如何计算算法的最坏情况时间复杂度

Question

你如何计算这个算法的最坏情况时间复杂度

for j = 1 to i do
     for k = 1 to j do 
         print(i,j,k)

Answer 1

由于我们没有条件会影响此算法的运行时间，因此复杂度将保持不变：始终具有相同的时间复杂度。

让我们保持简单。

如果我们只考虑内循环中的语义重要指令，我们可以计算复杂度如下：

每个外循环运行将下一个内循环运行计数加一。

我们会有 1 + 2 + 3 + 4 + 5 + ... + i-1 + i 循环运行s，每次外循环结束，内循环都会比之前多执行一次。

现在我们尝试概括这个表达式。

我们将初始术语加倍以另一种形式表示它，您会明白为什么。

2 * (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) = (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) + (1 + 2 + 3 + 4 + 5 + ... + i-1 + i)

2 * (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) = (1+i) + (2 + (i-1)) + (3 + (i-2)) + ... + ((i-1) + 2) + (i+1)

现在我们可以看到在这个表示中我们有多个相同的项。

2 * (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) = (1+i) + (1+i) + (1+i) + ... + (1+i) + (1+i)

2 * (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) = i*(1+i)

由于我们的初始复杂度仍然是原来的两倍，因此我们需要除以 2，从而得到封闭形式的表达式。

1 + 2 + 3 + 4 + 5 + ... + i-1 + i = (i*(1+i))/2

导致我们的复杂性O(i(i+1)/2) => O(i^2)

我们可以这样做，因为在 O() 中给定一个多项式，您可以简单地将其替换为 x^highest_power

我们不处理控制结构本身强制处理的指令；我不认为这是任务。如果您愿意，请告诉我。

如何计算算法的最坏情况时间复杂度

how to compute the worst case time complexity of a algorithm

data-structures

discrete-mathematics