python中的Big O符号 [英] Big O notation in python

问题描述

有人知道任何有用的资源来学习大符号吗?特别是学习如何遍历一些代码并能够看到它是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).

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

Also, some good websites I would recommend are: https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

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

And, a video from a lecture series from a Stanford professor: https://www.youtube.com/watch?v=eNsKNfFUqFo

这篇关于python中的Big O符号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！