Python big_o似乎返回了完全不正确的结果 - 我在做什么错？

Question

我正在比较使用 big_o 模块，对于以下方法，我的函数不会返回预期的结果：这是

1. ：

    def itertools_chain_from_iterable(arr): 
        return list(chain.from_iterable(arr))

返回“常数”，这可能是不正确的。

2. 这是：

    def merge_extend(self,arr):
        output = []
        for l in arr:
            output.extend(l)
        return output

（最多不应该是二次吗？

3. ）

    def merge_w_sum(self,arr): 
        return sum(arr,[])

返回“立方” //mathieularose.com/how-not-not-not-to-flatten-a-list-list-lists-lists-in-python#:%7e:text = we%20can%20Conclude%20that%20％20Sum(LST%2C%20%5B%5B%5B%5B%5B%5B% 5d）％20HAS％20季度％20综合性。％20综合％20to％3A“ rel =“ nofollow noreferrer”>在这里进行证明。

4. 此外，列表理解一个

    def merge_bucket(self,bucket):
        return [number for n in bucket for number in n]

返回“ polynomial”，这似乎很恐怖好吧）

用于计算复杂性的代码：

print('<function name>:', big_o.big_o(<function name>, 
       lambda n:[big_o.datagen.integers(9900,1,9999999) for n in range(50)],
       n_measures=20)[0])

输出：

complexity of itertools_chain_from_iterable: Constant: time = 0.0013 (sec)
complexity of merge_w_sum: Linear: time = 0.46 + 6.2E-07*n (sec)
complexity of merge_extend: Cubic: time = 0.048 + -2.3E-18*n^3 (sec)
complexity of merge_bucket: Polynomial: time = 0.2 * x^-0.019 (sec)

我在做什么（或理解）错误？

Answer 1

您的lambda忽略了其参数n，而始终产生相同的常数 size输入。大小的输入n。

（注意：最初的问题有8个功能，其中7个被判断为“恒定时间”。它被编辑为更大的常数，然后得到其他判断。我猜您的计算机的速度有些不稳定，因为恒定输入仍应引导为了持续的运行时间，因此在任何情况下都应该像我所说的那样固定输入的功能。）

鉴于它是二维n，或sqrt（n）sqrt（n）的列表。如果您的目标是证明sum（arr，[]）是不好的，则大概是尺寸1的n列表。例如：

lambda n: [[i] for i in range(n)]

一个完整​​程序：

import big_o
from itertools import chain

def chained(arr):
    return list(chain.from_iterable(arr))

def merge_extend(arr):
    output = []
    for l in arr:
        output.extend(l)
    return output

def merge_w_sum(arr): 
    return sum(arr,[])

def merge_bucket(bucket):
    return [number for n in bucket for number in n]

funcs = [
    (chained, 10**5),
    (merge_extend, 10**5),
    (merge_w_sum, 10**4),
    (merge_bucket, 10**5),
]

for _ in range(3):
    for func, max_n in funcs:
        complexity = big_o.big_o(
            func,
            lambda n: [[0]] * n,
            max_n=max_n,
            n_timings=10,
        )[0]
        print(
            f'{func.__name__:13}',
            complexity
        )
    print()

示例结果：

chained       Linear: time = 8.2E-05 + 5.8E-08*n (sec)
merge_extend  Linear: time = -4.2E-06 + 8.4E-08*n (sec)
merge_w_sum   Quadratic: time = 0.00013 + 2.4E-09*n^2 (sec)
merge_bucket  Linear: time = 0.00046 + 8E-08*n (sec)

chained       Logarithmic: time = -0.0075 + 0.0014*log(n) (sec)
merge_extend  Linear: time = -2E-05 + 8.5E-08*n (sec)
merge_w_sum   Quadratic: time = 0.00011 + 2.4E-09*n^2 (sec)
merge_bucket  Linear: time = -4.2E-05 + 2.6E-07*n (sec)

chained       Linear: time = -1.8E-05 + 1.6E-07*n (sec)
merge_extend  Logarithmic: time = -0.01 + 0.0019*log(n) (sec)
merge_w_sum   Quadratic: time = 8.3E-05 + 2.4E-09*n^2 (sec)
merge_bucket  Linear: time = 7.1E-05 + 8.3E-08*n (sec)

您可以在大多数时候看到它正确，但有时仍然会认为对数而不是线性。在更稳定的系统上，它可能会更好。较大的max_n值也应该有所帮助，但是我尝试了，然后big_o用一些已知内部错误。

另请注意，我为不同功能使用了不同的max_n值。所有人都使用同样的东西是不好的。如果您对所有人都使用相同的内容，那么如果它很大，则二次时间解决方案需要难以忍受的时间很长，如果它很小，线性时间解决方案花费的时间很少，以至于big_o很难区分它与对数或对数或对数或线性化。似乎没有一个对所有人有益的中等价值。理想情况下，big_o将适当地调整max_n，但我认为它不支持它。

Answer 2

首先，重要的是要了解 big o noreforge 是关于估计功能的渐近生长。

即当输入大小增长到无限时，它们如何“表现”。

例如，如果据说算法在 o（n^2）中运行，则（大致）
输入大小（ n ）生长到无穷大，执行时间将由恒定乘以 n^2 的束缚（有关更准确的定义，请参见上面的链接）。

因此，“真实的” Big -O与具体的时间测量无关（特别是因为我们无法测量无限输入） - 至少在理论意义上。

PYPI/BIG-O 之类的库尝试估计输入尺寸增长时处理时间的增长方式。
但这只是一个估计，在很大程度上取决于时间函数的属性和实际上给出的输入的大小。

就您而言，似乎您给了它太小的输入。
这导致了很短的执行时间，导致估计方法失败。
您可以尝试显着增加输入大小。

---

更新：最后一段（关于输入太小的原因）是一个猜测是错误的 - 请参见@kellybundy的答案上面。