アルゴリズムの時間複雑度 - nまたはn * n？

Question

私はこのアルゴリズムのシータの複雑さを見出そうとしています。 （aは整数のリストである）一方

def sttr(a): 
    for i in xrange(0,len(a)): 
     while s!=[] and a[i]>=a[s[-1]]: 
      s.pop() 
     s.append(i) 
    return s 

、私はappendがn（配列の長さ）が実行されていると言うことができ回、そうpopすぎて、私は検討すべき最後の事はありますwhile実行可能な条件はおそらく2n回である。

これは、このアルゴリズムが最大で4*nであると言うことができるので、THETA（n）です。

ただし、償却分析ではありませんか？一方

私はこれを言うことができます。

2つのネストされたサイクルがあります。 forサイクルは正確にn回実行されています。 whileサイクルは、最大でn回実行できます。これは、各繰り返しでアイテムを削除する必要があるためです。だから、複雑さはTHETA（n * n）です。

私はTHETAを計算したいが、これら2つのオプションのうちどれが正しいかわからない。アドバイスをいただけますか？

Answer 1

答えはTHETA(n)で、あなたの議論は正しいです。

これは償却分析ではありません。

償却分析を行うには、内部ループを調べる必要があります。アルゴリズムの残りの部分を無視すると、whileがどれほど速く実行されるかは簡単に言えません。ナイーブなアプローチはO（N）であり、それはそれが最大反復回数であるため正しい。しかし、実行の総数がO（N）（あなたの議論）であり、これがN回実行されることを知っているので、内部ループの複雑さはO（1）であると言うことができます。