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

この関数に渡されるリスト L のサイズを n とします。次のうち、n が大きくなるにつれてこの関数の実行時間がどのように大きくなるかを最も正確に説明しているのはどれですか?

(a) n のように直線的に増加します。(b) n^2 のように 2 次的に増加します。

(c) 直線的ではありません。(d) 二次以上に成長する。

関数の実行時間と n の増加との関係をどのように把握するのか理解できません。誰かが私にこれを説明してもらえますか?

4

6 に答える 6

12

わかりました、これは宿題なので：

これはコードです：

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

明らかに len(L) に依存します。

それでは、各行のコストを見てみましょう。

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

これらは明らかに一定時間であり、L に依存しません。ループには次のものがあります。

    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)

全体的な複雑さは

loops(L) * (timelookup(L) + const)

私はナイスガイなので、Python ではリスト ルックアップは一定であるため、要約すると次のようになります。

O(loops(L))(big-O 慣習が示すように、一定の要素は無視されます)

に基づいて、どのくらいの頻度でループしますlen()かL?

(a) リスト内の項目の数だけ (b) リスト内の項目の数だけ 2 次的に?

(c) リストに項目があるので頻度が低い (d) (b) より多い？

于 2012-04-23T20:43:47.440 に答える
10

私はコンピューター サイエンスの専攻ではなく、この種の理論をしっかりと理解しているとは言いませんが、私の観点から誰かが回答を試みて貢献することは適切であると考えました。

関数の実行には常に時間がかかります。可変長のリスト引数を操作している場合、その関数の実行にかかる時間は、そのリストにある要素の数に比例します。

長さ == 1 のリストを処理するのに 1 単位の時間がかかると仮定しましょう。質問が求めているのは、リストのサイズが大きくなるのと、この関数の実行にかかる時間の増加との関係です。

このリンクでは、Big O 表記の基本を説明しています: http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

iO(1) の複雑さ (実際には AD オプションの 1 つではありません) の場合、L のサイズに関係なく複雑さが増加しないことを意味します。明らかに、例では、カウンターの成長に依存する while ループを実行しています。が乗算されているという事実に注目し、iwhile ループを通過するのにかかる時間と L の長さの関係を示します。基本的に、while ループの数を比較してみてください。 loop は len(L) のさまざまな値で実行する必要があり、それによって複雑さが決まります。時間の 1 単位は、while ループの 1 回の繰り返しになります。

このテーマに関する専門知識が不足しているため、ここで何らかの形で貢献できたことを願っています。

更新
ch3ka からのコメントに基づいて明確にするために、ループ内で現在行っている以上のことを行っている場合は、withループごとに追加された複雑さも考慮する必要があります。しかし、あなたのリストのルックアップL[i]は一定の複雑さであり、それに続く数学であるため、複雑さの観点からそれらを無視することができます.

于 2012-04-23T19:57:55.190 に答える
4

これを見つけるための簡単な方法を次に示します。

import matplotlib.pyplot as plt

def f2(L):
    sum = 0
    i = 1
    times = 0
    while i < len(L):
        sum = sum + L[i]
        i = i * 2
        times += 1    # track how many times the loop gets called
    return times

def main():
    i = range(1200)
    f_i = [f2([1]*n) for n in i]
    plt.plot(i, f_i)

if __name__=="__main__":
    main()

...結果は

関数ループとパラメーター サイズのプロット

横軸は L のサイズ、縦軸は関数のループ回数です。big-O はこれから明らかになるはずです。

于 2012-04-23T20:10:16.870 に答える
3

長さn=10の入力で何が起こるかを考えてみましょう。ここで、入力サイズが2倍の20になったらどうなるかを考えてみましょう。ランタイムも2倍になりますか？それからそれは線形です。実行時間が4倍になると、2次式になります。等。

于 2012-04-23T20:16:01.097 に答える
2

関数を見るときは、リストのサイズが発生するループの数にどのように影響するかを判断する必要があります。

特定の状況で、nをインクリメントし、whileループが実行される回数を確認します。

n = 0, loop = 0 times
n = 1, loop = 1 time
n = 2, loop = 1 time
n = 3, loop = 2 times
n = 4, loop = 2 times

パターンを見ますか？今あなたの質問に答えてください、それをします：

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

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

経験的な結果については、ヒューの答えを確認してください:)

于 2012-04-23T20:13:16.997 に答える
0

リストルックアップは定数時間のO(log(len(L)))操作であるため、リストのサイズに依存しません。

于 2012-04-23T20:11:20.217 に答える