复杂度与 运行 时间内的实际增长不符？ (python)
Complexity does not match actual growth in running time? (python)
我运行 python中的2个代码然后测量complete.The代码所花费的时间非常简单，只是递归最大值。这里是：
1.
def max22(L, left, right):
if(left>=right):
return L[int(left)]
k = max22(L,left,(left+right-1)//2)
p = max22(L, (right+left+1)//2,right)
return max(k,p)
def max_list22(L):
return max22(L,0,len(L)-1)
def max2(L):
if len(L)==1:
return L[0]
l = max2(L[:len(L)//2])
r = max2(L[len(L)//2:])
return max(l,r)
第一个应该 运行 (imo) 在 O(logn) 中，第二个在 O(n*logn) 中。
但是，我测量了 n=1000、n=2000 和 n=4000 的 运行ning 时间，
不知何故，这两种算法的增长似乎都是线性的！这怎么可能？我是否弄错了复杂性，或者可以吗？
谢谢
第一个算法不是 O(log n)，因为它检查每个元素的值。可能显示为O(n)
至于第二个，可能你只是没有注意到 n 和 nlogn 在这么小的尺度上的区别。
仅仅因为一个函数将搜索 space 分成 2，然后递归地查看每一半并不意味着它在复杂度上有一个 log(n) 因子。
在您的第一个解决方案中，您将搜索 space 分成 2 个，但最终会检查每一半中的 每个 元素。与丢弃搜索的一半 space 的二进制搜索不同，您正在检查两半。这意味着不会从搜索中丢弃任何东西，您最终会查看每个元素，从而使复杂度为 O(n)。第二次实施也是如此。
您的第一个算法在普通机器上是 O(n)，因此您的测试表明这一点不足为奇。您的第二个算法是 O(n*log in)，但如果您使用适当的数组而不是列表，它将是 O(n)。由于 Python 内置列表操作非常快，您可能还没有达到对数减速；用更像 n=4000000 的值尝试一下，看看你得到了什么。
请注意，如果您可以 运行 两个并行递归调用（使用 O(1) 切片），则两种算法都可以 运行 在 O(log n) 时间内。当然，您需要 O(n) 个处理器来执行此操作，但如果您正在设计芯片而不是编写程序，那么这种缩放将很简单...
我运行 python中的2个代码然后测量complete.The代码所花费的时间非常简单，只是递归最大值。这里是： 1.
def max22(L, left, right):
if(left>=right):
return L[int(left)]
k = max22(L,left,(left+right-1)//2)
p = max22(L, (right+left+1)//2,right)
return max(k,p)
def max_list22(L):
return max22(L,0,len(L)-1)
def max2(L):
if len(L)==1:
return L[0]
l = max2(L[:len(L)//2])
r = max2(L[len(L)//2:])
return max(l,r)
第一个应该 运行 (imo) 在 O(logn) 中，第二个在 O(n*logn) 中。 但是，我测量了 n=1000、n=2000 和 n=4000 的 运行ning 时间， 不知何故，这两种算法的增长似乎都是线性的！这怎么可能？我是否弄错了复杂性，或者可以吗？ 谢谢
第一个算法不是 O(log n)，因为它检查每个元素的值。可能显示为O(n)
至于第二个，可能你只是没有注意到 n 和 nlogn 在这么小的尺度上的区别。
仅仅因为一个函数将搜索 space 分成 2，然后递归地查看每一半并不意味着它在复杂度上有一个 log(n) 因子。
在您的第一个解决方案中，您将搜索 space 分成 2 个，但最终会检查每一半中的 每个 元素。与丢弃搜索的一半 space 的二进制搜索不同，您正在检查两半。这意味着不会从搜索中丢弃任何东西，您最终会查看每个元素，从而使复杂度为 O(n)。第二次实施也是如此。
您的第一个算法在普通机器上是 O(n)，因此您的测试表明这一点不足为奇。您的第二个算法是 O(n*log in)，但如果您使用适当的数组而不是列表，它将是 O(n)。由于 Python 内置列表操作非常快，您可能还没有达到对数减速；用更像 n=4000000 的值尝试一下，看看你得到了什么。
请注意，如果您可以 运行 两个并行递归调用（使用 O(1) 切片），则两种算法都可以 运行 在 O(log n) 时间内。当然，您需要 O(n) 个处理器来执行此操作，但如果您正在设计芯片而不是编写程序，那么这种缩放将很简单...