1

アルゴリズムの時間計算量または理論上の実行時間を（擬似コードが与えられた場合）、T（n）として1行ずつ計算する必要があります。試してみましたが、混乱することがいくつかあります。たとえば、「if」ステートメントの時間計算量はどれくらいですか？そして、ネストされたループをどのように処理しますか？コメントされている私の試みと一緒にコードは以下にあります。

長さ[A]=n

    for i = 0 to length[A] - 1    // n - 1 
      k = i + 1                   // n - 2
      for j = 1 + 2 to length[A]  // (n - 1)(n - 3)
        if A[k] > A[j]            // 1(n - 1)(n - 3)
          k = j                   // 1(n - 1)(n - 3)
      if k != i + 1               // 1(n - 1)
        temp = A[i + 1]           // 1(n - 1)
        A[i + 1] = A[k]           // 1(n - 1)
        A[k] = temp               // 1(n - 1)
4

1 に答える 1

1

Blenderは正しいです、結果はO（n ^ 2）です：それぞれがに依存する反復カウントを持つ2つのネストされたループn。

より長い説明：

この場合、ifは実際には重要ではありません。O-notationはアルゴリズムの最悪の実行時間のみを調べるため、全体の実行時間よりも悪い実行パスを選択するだけです。あなたの例では、両方の実行パス（k != i+ 1trueまたはfalse）はランタイムにそれ以上の影響を与えないため、無視できます。の中に3番目のネストされたループがあり、これも実行されてnいるif場合、O（n ^ 3）になります。

行ごとの概要：

for i = 0 to length[A] - 1    // n + 1 [1]
  k = i + 1                   // n
  for j = 1 + 2 to length[A]  // (n)(n - 3 + 1) [1]
    if A[k] > A[j]            // (n)(n - 3)
      k = j                   // (n)(n - 3)*x [2]
  if k != i + 1               // n
    temp = A[i + 1]           // n*y [2]
    A[i + 1] = A[k]           // n*y
    A[k] = temp               // n*y

[1]forループステートメントはn+1回実行され、次の値が使用されますi:( 0true、ループを続行）、1（true、ループを続行）、...、length[A] - 1（true、ループを続行）、length[A]（false、ループを中断）

if[2]データを知らなくても、の条件が真である頻度を推測する必要があります。この推測は、変数0 <= x<= 1を導入することで数学的に行うことができます。これは、前に述べたことと一致しています。x独立しnているため、一定の要因としてのみ全体的な実行時間の複雑さに影響します。実行パス。

于 2013-01-23T12:12:17.460 に答える