为何Python itertools.combinations() amortized时间复杂度非O(1)？

CPython标准库中的itertools.combinations函数不具备O(1)均摊时间复杂度。在生成n个元素的k组合时，核心问题出现在k接近n的场景，此时会产生O(n)的均摊时间复杂度。

问题 #

1. Python核心开发者为何做出这样的设计选择？
2. 是否存在标准库或第三方代码能保证O(1)的均摊时间复杂度？

时间复杂度推导说明 #

关于得出O(n)均摊时间复杂度的简要推导：
在该函数的实现代码中，基准索引为i的组合数量为$\binom{n-k+i}{i+1}$，此类场景下的数组操作次数为3k-3i-1。将两者相乘并对所有可能的i值求和，得到总操作次数。除以组合总数$\binom{n}{k}$，最终得出均摊时间复杂度为O(n)。

重写的C语言迭代器实现 #

以下是一个独立的C代码，以迭代器风格重写了itertools.combinations函数，用于处理0到n-1的整数数组的k组合：

#include <stdlib.h> // malloc
#include <stdio.h> // printf
#include <stdbool.h> //bool, true, false

/* 测试工具函数 */
int* integersInOrder(int size){
    int* array = malloc(size * sizeof(int));
    for(int i=0; i < size; i++)
        array[i] = i;
    return array;
}

void printArray(int* array, int size){
    for(int i=0; i<size; i++)
        printf("%d ", (int)array[i]);
    printf("\n");
}

/* 模拟itertools.combinations的核心逻辑 */
static const bool IS_RUNNING = true, IS_DONE = false;

bool nextCombination(int* indices, int n, int k){
    if(k > n)
        return IS_DONE;
    
    bool isFound = false;
    int i;
    // 找到最右侧的非最大索引
    for(i = k - 1; i >= 0; i--){
        if(indices[i] != n - k + i){
            isFound = true;
            break;
        }
    }
    if(!isFound)
        return IS_DONE;
    
    // 将索引i的值加1
    indices[i]++;
    // 将i右侧的所有索引设置为字典序最小值
    for(int j = i + 1; j < k; j++)
        indices[j] = indices[j - 1] + 1;
   
    return IS_RUNNING;
}

/* 入口函数 */
int main()
{
    int n = 5, k = 3;
    int* array = integersInOrder(k);
    printArray(array, k);
    
    while(IS_RUNNING == nextCombination(array, n, k)){
        printArray(array, k);
    }

    return 0;
}

内容的提问来源于stack exchange，提问作者UnderscorePoY