pythonジェネレータ時間の複雑さの混乱

Question

私はキーワードyieldとジェネレータをPythonで読んでいますが、私はそれが時間の複雑さという用語を正しく理解しているかどうかを知りたいと思っています。今、私の理解が、これは時間Oの複雑さ（N ^を持っていることである

>>> for factor in calc_factor(100): # this is the first "for" loop 
     print factor 

：ここ

が要因得るために、私のジェネレータ関数である：

def calc_factors(n): 
    for k in range(0, n+1):  # this is the second "for" loop 
     if n % k == 0: 
      yield k 

を、私は、このジェネレータ関数を呼び出します2）それは2つのforループを持っているが、再び私は確信していない。この前に私を教えてください。 ありがとうございます！

Answer 1

あなたは間違っています。 O（n）ループがあります。ジェネレータ関数上のループはではなく、ネストされたループではなく、生成されたときにジェネレータから各アイテムを受け取るだけです。

つまり、for factor in calc_factor(100)ループは、が直接接続されています。からyield kの式です。 for factor in calc_factor(100)ループを実行するたびにループが1ステップ進みます。 yield k式が実行されるたびに1 factorの値が得られます。 yield kは（最大）n回実行します。

あなたは、あまりにも多くの真実を曲げずに、factor = kで、yield kラインを交換としてfor factor in calc_factor(100)ループ本体内のすべてのコードを想像することができます。あなたの場合はprint factorのみを使用するので、yield kをprint kに置き換えて機能を失うことはありません。

これを別の方法で見たい場合は、ジェネレータを取り出してリストを作成します。これはあなたのコードが、その場合に何をするかです：

results = [] 
for k in range(0, n+1): 
    if n % k == 0: 
     results.append(k) 

for factor in results: 
    print factor 

は今、あなたはまだ二つのループを持っている、しかし、彼らはネストされていません。 1つはリストを構築するためのO（n）ループであり、もう1つは結果を出力するためのO（k）ループ（k <）です。これは依然としてO（n）アルゴリズムになります。定数乗数は無視されます（あなたはO（2n） - > O（n）を持つでしょう）。

ジェネレータはすべてです。仲介リストを削除します。最初にすべての結果を収集する必要はなく、すぐに各結果にアクセスできます。

Answer 2

いいえ、これは時間複雑度O（n）のみを持つべきです。

for i in range(100):  # 100 times 
    for j in range(i): # i times, for *each* of the 100 values of i 
     # do something 

しかし、発電機、yield文原因と即時で：真のネストされたループでは

、外側のループのすべての反復は、内側ループの反復のフルセットを引き起こし発電機からの制御の復帰。だから、ジェネレータが反復されるたびに、とカウントされ、がジェネレータのループを通過します。

したがって、for factor in calc_factor(100):は、発電機のループのインスタンスごとに発電機を1回呼び出します。したがって、ある意味では、このはジェネレータのループです。それは発電機自体の外部から制御されているだけです。従って、でなく、外側入れ子ループです。