algorithm - 算法中的步数

Question

就 n 而言，该算法的步数是多少？

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

请在此处提及每个步骤的计数。谢谢！

Answer 1

查找步数的过程

首先定义步骤：

int mean(int a[], size_t n)

{

int sum = 0;                 // 1 step
for (int i = 0; i < n; i++)  // 1 step
    sum += a[i];             // 1 step
return sum;                  // 1 step
}

接下来根据 N 确定步骤的频率：

int mean(int a[], size_t n)

{
int sum = 0;                 // 1 step * 1
for (int i = 0; i < n; i++)  // 1 step * (N+1)
    sum += a[i];             // 1 step * N
return sum;                  // 1 step * 1
}

将步骤加起来：1 + (N+1) + N + 1

减少：2N + 3

扔掉不随 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)。

Answer 3

我希望这是您正在寻找的：

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

最坏的情况：将扫描整个数组，从a[n]to a[0]= O(n)

平均情况：将扫描半个数组 O(n/2) = O(n)

复杂度为 O(n)