python 中的大 O 表示法

有谁知道有什么学习大符号的好资源吗？特别是学习如何遍历一些代码并能够看到它会是 O(N^2) 或 O(logN)？最好能告诉我为什么这样的代码等于 O(N log N)

def complex(numbers):
    N = len(numbers)
    result = 0
    for i in range(N):
        j = 1
        while j < N:
            result += numbers[i]*numbers[j]
            j = j*2
    return result 

Thanks!

首先，让我向您定义 O(N log N) 是什么。这意味着该程序最多将运行 N log N 操作，即它的上限为 ~N log N（其中 N 是输入的大小）。

现在，你的 N 是数字的大小，或者你的代码：

N = len(numbers)

请注意，第一个 for 循环从 0 运行到 N-1，总共执行 N 次操作。这就是第一个 N 的来源。

-

那么，log N 从哪里来呢？它来自 while 循环。

在 while 循环中，不断将 2 乘以 j，直到 j 大于或等于 N。

当我们执行循环〜log2(N)次时，这将完成，它描述了我们必须将j乘以2才能得到N。例如，log2(8) = 3，因为我们将j乘以2 3次得到8：

#ofmult. j      oldj
  1      2  2 <- 1 * 2
  2      4  4 <- 2 * 2
  3      8  8 <- 4 * 2

为了更好地说明这一点，我在代码中为 i 和 j 添加了一条 print 语句：

def complex(numbers):
    N = len(numbers)
    result = 0
    for i in range(N):
        j = 1
        while j < N:
            print(str(i) + " " + str(j))
            result += numbers[i]*numbers[j]
            j = j*2
    return result 

当运行时：

>>> complex([2,3,5,1,5,3,7,3])

这是输出的内容：

0 1
0 2
0 4
1 1
1 2
1 4
2 1
2 2
2 4
3 1
3 2
3 4
4 1
4 2
4 4
5 1
5 2
5 4
6 1
6 2
6 4
7 1
7 2
7 4

注意我们的 i 如何从 0...7 （N 次，总共 O(N) ），第二部分，每个 i 总是有 3 个 ( log2(N) ) j 输出。 因此，代码的复杂度为 O(N log2 N)。

另外，我推荐的一些好的网站是：https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

还有斯坦福大学教授系列讲座的视频：https://www.youtube.com/watch?v=eNsKNfFUqFo https://www.youtube.com/watch?v=eNsKNfFUqFo