时间戳

首页 > 解决方案 > 求代码的大 O 时间复杂度

algorithm - 求代码的大 O 时间复杂度

问题描述

我非常熟悉关于常数、线性和二次时间复杂度的简单时间复杂度。在简单的代码段中，例如：

int i = 0;  
i + 1;

这是恒定的。所以 O(1)。在：

for (i = 0; i < N; i++)

这是线性的，因为它迭代 n+1 次，但是对于大 O 时间复杂度，我们删除了常数，所以只有 O(N)。在嵌套的 for 循环中：

for (i = 0; i < N; i++) 
  for (j = 0; j < N; j++)

我知道我们如何将 n+1 乘以 n 并达到 O(N^2) 的时间复杂度。我的问题是稍微复杂一点的版本。因此，例如：

S = 0;
for (i = 0; i < N; i++) 
  for (j = 0; j < N*N; j++) 
    S++;

在这种情况下，我是否会将 n+1 乘以内部 for 循环时间复杂度，我认为它是 n^2？所以时间复杂度是O(n^3)？

另一个例子是：

 S = 0;
 for (i = 0; i < N; i++)
   for (j = 0; j < i*i; j++) 
     for (k = 0; k < j; k++) 
       S++;

在这种情况下，我将其扩展并写出来，并意识到内部的中间 for 循环似乎以 n*n 的时间复杂度运行，而最内部的 for 循环以 j 的速度运行，也是 nxn。所以在那种情况下，我会乘以 n+1 xn^2 xn^2，这会给我 O(n^5) 吗？

此外，我仍在努力理解什么样的代码具有对数时间复杂度。如果有人能给我一个以 log(n) 或 n log(n) 时间复杂度执行的算法或代码段，并解释它，那将不胜感激。

标签： algorithmtime-complexitybig-o

解决方案

你所有的答案都是正确的。

对数时间复杂度通常发生在您在每次迭代中将问题的大小减小一个常数因子时。

这是一个例子：

for (int i = N; i >= 0; i /= 2) { .. do something ... }

在这个 for 循环中，我们将问题大小除以2每次迭代。log_2(n)在终止之前，我们需要大约迭代。因此，算法O(log(n))及时运行。

另一个常见的例子是二分搜索算法，它在一个排序的区间中搜索一个值。在这个过程中，我们在每次迭代中删除一半的值（再一次，我们将问题的大小减小了一个常数因子2）。因此，运行时间是O(log(n)).

推荐阅读