Python时间复杂度(运行时) [英] Python Time Complexity (run-time)

问题描述

def f2(L):
    sum = 0
    i = 1
    while i < len(L):
        sum = sum + L[i]
        i = i * 2
    return sum

让n为传递给此函数的列表L的大小.以下哪一项最准确地描述了该函数的运行时间如何随着n的增长而增长?

Let n be the size of the list L passed to this function. Which of the following most accurately describes how the runtime of this function grow as n grows?

(a)它像n一样线性增长.(b)它像n ^ 2一样平方增长.

(a) It grows linearly, like n does. (b) It grows quadratically, like n^2 does.

(c)它的增长小于线性增长.(d)它的增长超过平方.

(c) It grows less than linearly. (d) It grows more than quadratically.

我不明白您如何弄清楚函数的运行时间与n的增长之间的关系.有人可以向我解释一下吗?

I don't understand how you figure out the relationship between the runtime of the function and the growth of n. Can someone please explain this to me?

推荐答案

好的，因为这是家庭作业:

ok, since this is homework:

这是代码:

def f2(L):
    sum = 0
    i = 1
    while i < len(L):
        sum = sum + L[i]
        i = i * 2
    return sum

它显然取决于len(L).

it is obviously dependant on len(L).

因此，让我们看一下每一行的成本:

So lets see for each line, what it costs:

sum = 0
i = 1
# [...]
return sum

显然，这些时间是恒定的，与L无关.在循环中，我们有:

those are obviously constant time, independant of L. In the loop we have:

    sum = sum + L[i] # time to lookup L[i] (`timelookup(L)`) plus time to add to the sum (obviously constant time)
    i = i * 2 # obviously constant time

，循环执行了多少次?它显然取决于L的大小.让我们称之为 loops(L)

and how many times is the loop executed? it's obvously dependant on the size of L. Lets call that loops(L)

所以总体复杂度为

循环(L)*(timelookup(L)+ const)

作为我的好人，我会告诉您列表查找在python中是恒定的，因此归结为

Being the nice guy I am, I'll tell you that list lookup is constant in python, so it boils down to

O(loops(L))(常数变量被忽略，正如big-O约定所暗示的那样)

O(loops(L)) (constant factors ignored, as big-O convention implies)

以及您基于[code> L 的 len()循环的频率是多少?

And how often do you loop, based on the len() of L?

(a)与列表中的项目一样多(b)与列表中的项目一样多?

(a) as often as there are items in the list (b) quadratically as often as there are items in the list?

(c)的频率较低，因为(d)列表中的项目比(b)频率更高?

(c) less often as there are items in the list (d) more often than (b) ?

这篇关于Python时间复杂度(运行时)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！