O(n)+ O(n)= O(n)? [英] O(n) + O(n) = O(n)?

问题描述

根据O'Reilly的《 Python in Nutshell》中的Alex Martelli的说法，复杂度类为 O(n)+ O(n)= O(n).所以我相信.但是很困惑.他说:"N的两个线性函数之和也是N的线性函数."

According to Alex Martelli in O'Reilly's Python in a Nutshell, the complexity class O(n) + O(n) = O(n). So I believe it. But am confused. He explains it by saying that, "the sum of two linear functions of N is also a linear function of N."

根据维基百科，在功能分析中，线性函数是线性映射，例如就是 f(x + y)= f(x)+ f(y).找到了似乎更简单的定义，此处简单地说，线性函数是一个函数，其图形是一条直线."而且其中还包含一些比Wikipedia文章看起来更神秘的例子.

According to wikipedia, in functional analysis a linear function is a linear map, an example of which would be f(x+y) = f(x) + f(y). Found what seems to be a simpler definition here simply stating, "a linear function is a function who's graph is a straight line." And it includes a few more examples that are less esoteric-looking than the wikipedia article ones.

y = f(x) = a + bx

和:

y = 25 + 5x

let x = 1
then
y = 25 + 5(1) = 30

let x = 3
then
y = 25 + 5(3) = 40

也许可以公平地期望两个线性方程式的总和可以在一条图中表示为一条直线，该直线与表示每条直线的平均值相似.

Maybe it would be fair to expect that the sum of two linear equations could be represented on a graph as a straight line which shows something similar to an average between the straight lines that would represent each one.

我是否正确理解，即使在以下两个函数中，复杂"函数的处理时间是简单"函数的三倍，它们每个都以big-O表示为O(n)，因为处理时间的弧线将由图形/图形上的直线，对角线表示，而时间差将由以下事实表示:在图形表示中，更复杂的函数的角度会更锐利?/p>

So am I understanding correctly that even though in the following two functions, the "complex" function takes three times as long to process as the "simple" one, they each function in big-O notation as O(n), because the arc of the processing time would be represented by a straight, diagonal line on a plot/graph, and the time difference would be represented by the fact that on a graphic representation, the angle of the more complex function would be sharper?

from timer import Timer

def complex(it):
    result = []
    for i in it:
        result.append(i)
    result.reverse()
    return result

def simple(it):
    result = list(it)

longlist = list(range(0, 1000000))

with Timer() as t:
    reverse_(longlist)
print "=> elapsed time reverse: %s." % t.secs

with Timer() as t:
    straight(longlist)
print "=> elapsed time straight: %s" % t.secs

推荐答案

该语句是正确的，因为两个线性函数的加法也是线性函数.以下面两个为例:

The statement is correct, because the addition of two linear functions is also a linear function. Take for example these two:

y = 6*x + 10
y = 20*x + 2

将它们加在一起，您将得到:

Add them together and you get:

y = 26*x + 12

这也是一个线性函数！这适用于任何两个线性函数.

Which is also a linear function! This holds for any two linear functions.

y = A*x + B
y = C*x + D
-----------
y = (A+C)*x + (B+D)

这篇关于O(n)+ O(n)= O(n)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！