algorithm - 先验分析中少数陈述的数量级

Question

如果我们在循环中有以下语句，

1. n = n/3

2. n = n-1

3. n = n-2

我想知道如果我们有上面的语句，它们的数量级是多少，然后它们的大O符号怎么写？

我在谷歌上搜索了这些声明，但没有得到任何好的结果。如果您有任何链接，请引用我。

Answer 1

我。有点心灵感应

让我们假设所有循环都是这样的:

n = <initial value>;
while (n >= 1) {
    <insert statement here>;
}

二。空间复杂度

所有这些循环的空间复杂度都是O(1)。

为什么？因为这些循环在执行时占用的 RAM 和磁盘空间都取决于 n 的值。

三。时间复杂度

1。 n = n/3

很明显，在第 k 次循环迭代中，k ≥ 1，结果值 n' 应变为 n ' = n/3^k。 所以要找到k，我们要求解方程:

1 = n / 3^k    =>
3^k = n        =>
k = log3(n) = log(n) / log(3)

只要1/log(3)是有限常数，最终答案就是O(log(n))。

2。 n = n – 1

这是三种情况中最简单的一种。

n = 1 只有 1 次循环迭代，n = 2 有两次，依此类推。 O(n)。

3。 n = n – 2

对于 n = 1 和 n = 2，迭代次数为 1，对于 n = 3 和 n = 4 它等于 2，依此类推。因此，k = ⌈ n/2 ⌉。

O(⌈ n/2 ⌉) = O(n/2) = O(n)。