算法中的步数计算

Question

这个算法的步数与 n 的关系是多少？

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

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

- user2377778

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)

- samaksh shrivastava

Answer 2

我希望这就是您要找的内容：

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

最坏情况：需要扫描整个数组，从a[n] 到 a[0] = O(n)

平均情况：需要扫描一半的数组O(n/2) = O(n)

时间复杂度为O(n)

- Exceptyon

---

我正在寻找像6n+4，4n+6等答案... :( 我是新手，想要一点帮助来找出步骤计数过程。 - user2377778

应该是：1+1+n+n+1 = 2n+3 - Exceptyon

Answer 3

这是你步数的分析：

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)。

- Sazzadur Rahaman