if/elif/else文を使った関数のO（n^3）複雑度

Question

次の擬似コードを考えてみましょう。 if/else/ifステートメントがあります。各条件分岐内には、トリプルネストされたforループがあります。この文の複雑さはO（n^3）なので、関数は1つのパス（つまり、if、elifなど）を取ることができるか、それより複雑です。

def myFunction(myVariable, myList): 
    if myList == conditionOne: 
     for sublist in myList: 
      for element in sublist: 
       for char in element: 
        print(char) 
    elif myList == conditionTwo: 
     for sublist in myList: 
      for element in sublist: 
       for char in element: 
        print(char) 
    else: 
     for sublist in myList: 
      for element in sublist: 
       for char in element: 
        print(char) 

Answer 1

これはそれよりも複雑ですが、条件付きのためではありません。あなたの現在のコードはすべてのブランチで同じことをしますが、あなたの本当のコードはおそらくまったく同じようには見えませんが、良い近似であるかもしれません。この場合、難しさは他の場所から完全に生じます。

現在のコードの複雑さは、すべてのサブリストのすべての要素の長さの合計です。 nがmyListの長さの上限である場合、sublistとelementの場合、これはO（n3）になります。そうでない場合は複雑になる可能性があります。

別の簡単な特殊なケースは次のとおりです。

• myListは長さnを持っています。
• すべてsublistは、最大でもmです。
• すべてelementは、最大でもkです。

次に、あなたの複雑さが陽性であることがn、mとkと仮定すると、O（NMK）となります。

Answer 2

私は、あなたの関数の時間計算量がリストmyListの長さに依存するだけでなく、依存するだけでなく、あなたがnリストmyList（サブリストの数）の長さであると仮定したとします。

• 各サブリストの最大長さ（各サブリスト内の要素の最大数 - 各分岐条件の2 for-loop）

• 各要素の最大長さ（各要素における文字の数 - 3 for-loop）

正確に、n、m、pは、それぞれリストの長さは、各サブリストの最大長さ、及びある場合各要素の最大長さ、最悪の場合、アルゴリズムの時間複雑さはO（n * m * p）です。

Answer 3

このコードの複雑さは実際にはO(1)です。どの条件が真で、リスト、サブリスト、要素の長さは何ですか？最初の文字を読んだ後はすぐに戻ります。それは間違いだとあなたが実際にすべての文字を反復処理している場合

、それはn何であるかに依存するだろう、とそれを定義する2つの一般的な方法があります：通常

1. 時間の複雑さについて話して、我々はそれを定義します入力の点で。ここでは、あなたのアルゴリズムは（すべての要素を反復していると仮定して）入力の大きさが線形であるので、複雑さは実際にはO(n)です。あなたはmylistにおけるサブリストの数ではなく、入力の大きさ、及び各サブリストはmの要素を持っているINHに加え、長さk（平均上のすべて）の各としてnを参照する場合Run-time analysis is a theoretical classification that estimates and anticipates the increase in running time (or run-time) of an algorithm as its **input size (usually denoted as n) increases**....
2. ：wikipediaから。次に、複雑さはO(n*m*k)