4

コンピューティング クラスの 1 つに関する質問に答えています。アルゴリズムを開発したところ、アルゴリズムの複雑さを尋ねられました。今のところ複雑さを判断するのが得意ではないので、誰でも確認できますか?

コードは次のとおりです。

if( A.type is not Comparable ): return False                   // Max runs = 1
current ← A.head                                               // Max runs = 1
printedFirst ← False                                           // Max runs = 1
while( current.hasNext ):                                      // Max runs = s-1
    if ( current.value < current.next.value ):                 // Max runs = s-1 
        if ( printedFirst ): print “, “                        // Max runs = s-1
        print “(“ + current.value + “, “ + current.next.value + “)” //runs = s-1
        printedFirst ← True                                    // Max runs = s-1
    current = current.next                                     // Max runs = s-1

だから私たちは持っています

3( 1 ) + 6(s - 1) = 3 + 6s - 6 = 6s - 3 = O( n )

正しい？

4

1 に答える 1

5

内部に単一の if がある単一の while ループ... O(n) に進みます。

あなたのクラスで頑張ってください。

于 2012-10-15T21:18:18.440 に答える