6 
def filter(f, lst):     
    if lst == []: return []
    if f(lst[0]): return [lst[0]] + filter(f, lst[1:])
    return filter(f, lst[1:]) 

def my_reverse(lst):        # Reverse the list
    def reverse_helper(x,y):
        if x == []: return y
        return reverse_helper(x[1:], [x[0]] + y)
    return reverse_helper(lst, []) 

def revfilter_alpha(f, lst):    # Reverse and filter ...
    return my_reverse(filter(f, lst))

def revfilter_beta(f, lst): # Reverse and filter ...
    if lst == []: return []
    return revfilter_beta(f, lst[1:]) + ([lst[0]]  if f(lst[0])  else [])

これらの Big Θ 表記で実行時間を決定する方法を誰かに説明してもらえますか? 私はかなりの数のことを読みましたが、まだどこから始めればよいかわかりません.

ではfilter、サイズ n のリスト内の各要素を、n 回の再帰呼び出しで述語関数 f を使用して n*n でチェックするため、Θ(n^2) だと思います。

revfilter_betaフィルタリング中に反転するだけでかなり似ているので、これもΘ（n ^ 2）ではありませんか？

revfilter_alphaは逆にフィルタリングするので、これは n^2*n^2 = Θ(n^4) ではないでしょうか?

誰か考えがありますか？

4

2 に答える 2

5

filter再帰呼び出しがnありますが、各反復でコピー操作も行うnため、最終的に Θ(n^2) になります。ただし、「適切に」実装した場合は、 Θ(n) になるはずです。

についても同じですmy_reverse。

についても同じですrevfilter_beta。

revfilter_alphafiltera を実行してからa を実行するだけなreverseので、 Θ(n^2 + n^2) = Θ(n^2) になります。

filter編集:もう少し調べてみましょう。

把握したいのは、入力のサイズに対して実行される操作の数です。O(n)最悪の場合、n操作の順序で行うことを意味します。たとえば、O(n/2)操作を行うことができるため、「の順序で」と言いますO(4n)が、最も重要な要素はnです。つまり、 がn成長するにつれて、一定の要因はますます重要性が低くなるため、非一定の要因 (nこの場合) のみを調べます。

filterでは、 size のリストに対していくつの操作が実行されるnでしょうか?

下から見ていきましょう。n0 - 空のリストの場合はどうなりますか? その後、空のリストが返されます。これが 1 つの操作であるとしましょう。

1の場合nは？含める必要があるかどうかlst[0]をチェックします - そのチェックは呼び出すのに時間がかかりますf- そしてリストの残りをコピーし、そのコピーに対して再帰呼び出しを行います。この場合は空のリストです。操作はsofilter(1)かかり、はリストをコピーするのにかかる時間であり、は要素を含める必要があるかどうかを確認するのにかかる時間です。ただし、各要素に同じ時間がかかると仮定します。f + copy(0) + filter(0)copy(n)f

どうfilter(2)ですか？1 つのチェックを実行してから、リストの残りをコピーし、残りを呼び出しfilterますf + copy(1) + filter(1)。

その模様はすでにご覧いただけます。filter(n)かかります1 + copy(n-1) + filter(n-1)。

今、copy(n)ちょうどですn-nそのようにリストをスライスするには操作が必要です。したがって、さらに単純化できますfilter(n) = f + n-1 + filter(n-1)。

これで、何回か展開してfilter(n-1)何が起こるかを確認できます。

filter(n) = f + n-1 + filter(n-1)
          = 1 + n-1 + (f + n-2 + filter(n-2))
          = f + n-1 + f + n-2 + filter(n-2)
          = 2f + 2n-3 + filter(n-2)
          = 2f + 2n-3 + (f + n-3 + filter(n-3))
          = 3f + 3n-6 + filter(n-3)
          = 3f + 3n-6 + (f + n-4 + filter(n-4))
          = 4f + 4n-10 + filter(n-4)
          = 5f + 5n-15 + filter(n-5)
          ...

x繰り返しを一般化できますか? その1, 3, 6, 10, 15... シーケンスは三角形の数字です。つまり1、 、1+2、1+2+3、などです。 からまで1+2+3+4のすべての数字の合計は です。1xx*(x-1)/2

          = x*f + x*n - x*(x-1)/2 + filter(n-x)

さて、何xですか？何回繰り返しますか？x=の場合、再帰 - = =nがなくなることがわかります。したがって、式は次のようになります。filter(n-n)filter(0)1

filter(n) = n*f + n*n - n*(n-1)/2 + 1

さらに単純化できます。

filter(n) = n*f + n^2 - (n^2 - n)/2 + 1
          = n*f + n^2 - n^2/2 + n/2 + 1
          = n^2 - n^2/2 + f*n + n/2 + 1
          = (1/2)n^2 + (f + 1/2)n + 1

これで、かなり詳細な分析ができました。それは...が取るに足らない（たとえば= 1）とΘ((1/2)n^2 + (f + 1/2)n + 1)仮定すると、 になります。ffΘ((1/2)n^2 + (3/2)n + 1)

copy(n)ここで、直線的な時間ではなく一定の時間がかかった場合 (copy(n)が ではなく 1 の場合n)、そのn^2用語はそこに含まれないことに気付くでしょう。

私がΘ(n^2)最初に言ったとき、私はこれをすべて頭の中でやったわけではないことを認めます. むしろ、私は次のように考えました:わかりました、n再帰的なステップがnあり、copy. n*n = n^2、したがってΘ(n^2)。それをもう少し正確に行うには、n各ステップで縮小するため、実際にはn + (n-1) + (n-2) + (n-3) + ... + 1、上記と同じ図n*n - (1 + 2 + 3 + ... + n)= n*n - n*(n-1)/2=になります。これは、上記の の代わりに(1/2)n^2 + (1/2)n使用した場合と同じです。同様に、ステップがあり、各ステップが代わりに実行された場合 (リストをコピーする必要がなかった場合)、、時間、または単に.0fn1n1 + 1 + 1 + ... + 1nn

しかし、それにはもう少し直感が必要なので、何にでも適用できる力ずくの方法もお見せしたいと思います。

于 2012-10-11T01:39:39.000 に答える
2

すべての関数は、再帰ステップごとに時間O(N^2)がかかり、 length のリストにステップがあるためです。O(N)NN

関数で実行している 2 つの高価な (つまり、O(N)) 操作があります。1 つ目はスライスです (例: lst[1:])。2 つ目は、リスト連結 (+演算子を使用) です。

主に Python のリストは他の言語のリスト データ型とは異なるため、どちらも予想よりもコストがかかる可能性があります。内部的には、それらはリンクされたリストではなく、配列です。リンクされたリストに対して上記の操作を O(1) 時間で実行できます (ただし、O(1)スライスは破壊的です)。たとえば、Lisp では、使用したアルゴリズムはO(N)ではなく になりO(N^2)ます。

再帰は、末尾呼び出しの除去がないため、Python では最適ではないことがよくあります。sys最近のバージョンでは、Python のデフォルトの再帰制限は 1000 であるため、モジュールをいじって制限を増やさない限り、リストが長いと純粋に再帰的なソリューションが機能しなくなります。

これらのアルゴリズムのバージョンを Python でも実行することは可能ですO(N)が、上記のコストのかかるリスト操作はできるだけ避けたいと思うでしょう。再帰ではなく、より「pythonic」なスタイルのプログラミングであるジェネレーターを使用することをお勧めします。

ジェネレータを使用したフィルタリングは非常に簡単です。組み込みfilter関数はすでにそれを行っていますが、ほんの数行で独自の関数を書くことができます:

def my_filter(f, iterable):
    for e in iterable:
        if f(e):
            yield e

ソースでランダムアクセスを行うか、余分なスペースを使用できるようにする必要があるため、物事の順序を逆にすることはもう少し複雑ですO(N)（リストはシーケンスプロトコルに従い、ランダムにすることができますが、アルゴリズムはそのスペースにスタックを使用しますアクセス）。組み込みreversed関数はシーケンスでのみ機能しますが、任意のイテラブル (別のジェネレーターなど) で機能するバージョンを次に示します。

def my_reversed(iterable):
    storage = list(iterable)  # consumes all the input!
    for i in range(len(storage)-1, -1, -1):
        yield storage[i]

多くのジェネレーターとは異なり、これは出力を生成し始める前に一度にすべての入力を消費することに注意してください。無限の入力で実行しないでください!

これらはどちらの順序でも構成でき、my_reversed(filter(f, lst))同等である必要がありますfilter(f, my_reversed(lst))(ただし、後者の場合は、組み込みreversed関数を使用する方がおそらく優れています)。

上記の両方のジェネレーター (およびいずれかの順序での構成) の実行時間は になりますO(N)。

于 2012-10-11T02:38:08.773 に答える