algorithm - アルゴリズムのステップ数

Question

n で表したこのアルゴリズムのステップ数は?

SequentialSearch(a,x,n)
{
    i=n;
    a [0]=x;
    while(a [i]!= x) do
        i = i-1
    return i
}

ここに各ステップのカウントを記載してください。ありがとうございます!

Answer 1

これがあなたが探しているものであることを願っています：

while (a[i] != x) i = i-1;

最悪の場合:a[n]からa[0]= O(n)まで、配列全体をスキャンします

平均的なケース:半分の配列をスキャンします O(n/2) = O(n)

複雑さは O(n)

Answer 2

歩数の分析は次のとおりです。

SequentialSearch(a,x,n)
{
   i=n;    // 1 assignment operation 
   a [0]=x; // 1 assignment operation 
    while(a [i]!= x) do  // n number of comperison (worst case)
       i = i-1 // n number of decrement operation (worst case)
    return i // 1 return 
}

最悪の場合:2n + 3操作の数。最悪の場合、操作の数は入力配列のサイズ (n) に線形に関連するためです。したがって、アルゴリズムの実行時の複雑さは ですO(n)。