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

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

解释：

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

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

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

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

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

复杂度为 O(log n)。

Easiest way to calculate time complexity?