algorithm - 计算时间复杂度的最简单方法？

Question

我发现计算大多数问题的时间复杂度非常容易，但我的教授给出了非常复杂的例子，我很难弄明白。以下是他给我们的两个我无法深入了解的信息:

示例 1:

x = 0
j = n
while (j >= 1)
    for i = 1 to j do
        x += 1
    j *= 3/4
return x

示例 2:

x = 0
j = 3
while (j <= n)
    x += 1
    j *= j
return x

请注意，对于像 x += 1 和 j *= j 这样的操作，我们只将其计为 1 个时间单位。

如果你能告诉我你将如何计算这些例子的时间复杂度，我应该能够推断出我将如何计算他给出的大部分例子。谢谢!

Answer 1

答案:

1. O(j)
2. O(log log(n))

解释:

1. 查看内部循环。它在第一个条目中运行了 j 次。现在，j=3j/4。因此，第二次，它运行了 3j/4 次。第 3 次，9j/16，依此类推。操作总数将为:

   j + 3j/4 + 9j/16 + ...= 4j

因此，复杂度为 O(4*j) = O(j)。

1. 只有一个循环。其 Controller (j) 的值增加为:

   3、9、81、6561、...

现在，在达到特定数量 n 之前它将进行的迭代次数将是 log log (n)。如果每次都增加 3 的倍数，比如:

3, 9, 27, 81, 243...

复杂度为 O(log n)。