-1

Here's the algorithm:

Let a = 30, i = 1
While i < n
    For j = i+1 to n
        If ABS[(j*i)+20] < a then a = ABS[(j*i)+20]
    i = i + 1
Return k

Whats the number of steps this algorithm will take for the general case where the input is of size n? How do you work that out?

Also does this algorithm come under the quadratic complexity class?

4

3 回答 3

1

我认为这是与O(n^2)

我们有

n+(n-1)+(n-2)+(n-3)......[total n] ....3.2.1

如果我们计算它，它将是

0.5( (n^2) + n) = C (n^2 + n)

它是二次复杂度类。

于 2013-04-11T21:48:30.450 回答
0

让 f(i) 表示内部 for 循环运行的次数，假设 j 从 i+1 变为 n。例如 f(5) = n - 5 + 1，因为 j 经过 6,7,...,n。所以我们想要 f(1) + f(2) + f(3) + ... + f(n - 1)。计算每个 f(i) 的内容，然后将它们相加得到确切的答案。

通常有一个运行 n 次的外循环，然后内循环最多运行 n 次，复杂度上限为 ???

于 2013-04-11T21:29:22.610 回答
0

如果我是编译器，我会注意到这段代码只改变i, j, 和a, 局部变量；并且随后使用其值的唯一变量是k。所以我会逐渐优化除此之外的所有内容：

Return k

并且计算都是恒定的时间，只有几条机器指令。因此也在二次时间内。

于 2013-04-11T21:34:32.317 回答