有人知道学习大 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
首先，让我为您定义一下O(N log N)是什么。它意味着程序最多运行N log N次操作，即其上限为~N log N（其中N是输入的大小）。
现在，在这里，您的N是数字或代码的大小：
N = len(numbers)
-
那么，log N 是从哪里来的呢？它来自于 while 循环。
在 while 循环中，你不断将 2 乘以 j，直到 j 大于或等于 N。
这将在我们执行循环 ~log2(N) 次后完成，描述了我们必须将 j 乘以 2 多少次才能到达 N。例如，log2(8) = 3，因为我们将 j 乘以 2 三次以获得 8：
#ofmult. j oldj
1 2 2 <- 1 * 2
2 4 4 <- 2 * 2
3 8 8 <- 4 * 2
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
当你将j乘以2时，实际上是在说“我已经解决了剩余问题的一半！”在while循环的每个步骤中，您都在解决剩余问题的一半。因此，如果您的问题大小为x，则所需的迭代次数将为i = log_2 x，我们只需说是log x。在这种情况下，您的x只等于N。
for循环让您再次执行上述部分N次，因此您会得到N * log N。
我们使用O（N log N）表示，在每个步骤中，我们可能会做任何恒定数量的事情（例如，在while循环内部，我可能会执行十亿次操作），但我们不关心这个常数，因为通常N通常更大，并且可以任意变大（超过某个大小点后，即使十亿与N相比也微不足道，即谷歌）。因此，我们有O（N log N）。
这里有一个短暂的崩溃课程，以pdf形式呈现：
http://www1.icsi.berkeley.edu/~barath/cs61b-summer2002/lectures/lecture10.pdf
这是一堂短暂的速成课：