有人知道任何有用的资源来学习大符号吗?特别是学习如何遍历一些代码并能够看到它是O(N ^ 2)还是O(logN)?最好能告诉我为什么这样的代码等于O(N log N)
Does anyone know of any good resources to learn big o notation? In particular learning how to walk through some code and being able to see that it would be O(N^2) or O(logN)? Preferably something that can tell me why a code like this is equal to 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是输入的大小).
To start, let me define to you what O(N log N) is. It means, that the program will run at most N log N operations, i.e. it has a upper bound of ~N log N (where N is the size of the input).
现在,您的N是数字的大小或代码:
Now here, your N is the size of numbers, or your code:
N = len(numbers)请注意,第一个for循环从0到N-1,总共进行N次操作.这是第一个N的来源.
Notice that the first for loop runs from 0 to N-1, for a total of N operations. This is where the first N comes from.
-
那么,日志N从何而来?这是来自while循环.
Then, where does the log N come from? It is from the while loop.
在while循环中,您将2乘以j,直到j大于或等于N.
In the while loop, you keep multiplying 2 to j until j is greater or equal than N.
这将在执行循环〜log2(N)次后完成,该循环描述了我们必须将j乘以2才能达到N.例如,log2(8)= 3,因为我们乘以j乘以2的三倍得到8:
This will be completed when we have executed the loop ~log2(N) times, which describes how many times we have to multiply j by 2 to get to N. For example, log2(8) = 3, because we multiply j by 2 three times to get 8:
#ofmult. j oldj 1 2 2 <- 1 * 2 2 4 4 <- 2 * 2 3 8 8 <- 4 * 2为了更好地说明这一点,我在您的代码中为i和j添加了一条打印语句:
To better illustrate this, I have added a print statement in your code, for i and j:
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(总共O(N)次N次)开始,第二部分,每个i始终有3个(log2(N))j输出.因此,代码为O(N log2 N).
Notice how our i goes from 0...7 (N times for a total of O(N) ), and the second part, there are always 3 ( log2(N) ) j-outputs for every i. So, the code is O(N log2 N).
此外,我会推荐一些好的网站: rob-bell/2009/06/a-beginners-guide-to-big-o-notation/
Also, some good websites I would recommend are: rob-bell/2009/06/a-beginners-guide-to-big-o-notation/
还有斯坦福大学教授的一系列演讲视频: www.youtube/watch?v=eNsKNfFUqFo
And, a video from a lecture series from a Stanford professor: www.youtube/watch?v=eNsKNfFUqFo
更多推荐
python中的Big O符号
发布评论