0

我正在阅读一些关于时间复杂度的信息，我对如何实现以下时间复杂度以及是否有一组特定的规则或方法来解决这个问题感到非常困惑？

1)

Input: int n
for(int i = 0; i < n; i++){
   print("Hello World, ");
}
for(int j = n; j > 0; j--){
   print("Hello World");
}
  • 紧：6n + 5
  • 大O：O（n）

2)

Input: l = array of comparable items
Output: l = array of sorted items
Sort:
for(int i = 0; i < l.length; i++){
     for(int j = 0; j < l.length; j++){
         if(l{i} > l{j}){
} }
     Swap(l{i},l{j});
}
return ls;
  • 最坏情况时间复杂度：4n2 +3n+2 = O(n2)
4

3 回答 3

5

对于给定的算法，时间复杂度Big O是一种提供与给定输入大小相关的“算法执行的总基本操作”的足够公平估计的方法。n

1型

假设你有一个这样的算法：

a=n+1;
b=a*n;

上面的代码中有 2 个基本操作，不管你n有多大，对于上面的代码，计算机总是会执行 2 个操作，因为算法不依赖于输入的大小，所以上面的 Big-O代码是 O(1)。

2型

对于此代码：

for(int i = 0; i < n; i++){
   a=a+i;
}

我希望你理解 O(n) 中的 Big-O，因为基本操作数直接取决于n

3型

现在这段代码怎么样：

//Loop-1
for(int i = 0; i < n; i++){
   print("Hello World, ");
}
//Loop-2
for(int i = 0; i < n; i++){
   for(int j = 0; j < n; j++) {
       x=x+j;
   }
}

如您所见，loop-1 是 O(n)，loop-2 是 O(n^2)。所以感觉总复杂度应该是 O(n)+O(n^2)。但是没有，上面代码的时间复杂度是O(n^2)。为什么？因为我们试图知道算法在给定输入大小下执行的基本操作的足够数量，这对于其他人n来说相对容易理解。按照这个逻辑，O(n)+O(n^2) 变成 O(n^2)，或者 O(n^2)+O(n^3)+O(n^4) 变成 O(n^4) ）！

再次，您可能会问：但是如何？当我们将 Big-O 的所有低功率添加到 Big-O 的更高功率时，如何变得如此微不足道，以至于当我们向另一个人描述我们算法的复杂性时，我们可以完全忽略它们（低功率）？

我将尝试说明这种情况的原因：O(n)+O(n^2)=O(n^2)。

假设 n=1000，那么 O(n) 的准确计数是 1000 次操作，O(n^2) 的准确计数是 1000*1000=1000000，所以 O(n^2) 比 O(n) 大 1000 倍)，这意味着您的程序将在 O(n^2) 中花费大部分执行时间，因此不值得一提的是您的算法也有一些 O(n)。

PS。请原谅我的英语:)

于 2013-04-29T14:03:04.423 回答
4

在第一个示例中，数组有 n 个元素，并且您遍历这些元素两次。第一次从索引 0 开始直到 i，第二次从索引 n 开始到 0。所以，为了简化这一点，我们可以说它花了 2n。在处理大 O 表示法时，您应该记住我们关心边界：

结果，O(2n)=O(n) 和 O(an+b)=O(n)

Input: int n                        // operation 1
    for(int i = 0; i < n; i++){    // operation 2
    print("Hello World, ");       // Operation 3 
   }
for(int j = n; j > 0; j--)       // Operation 4
   {
   print("Hello World");        //Operation 5
    }

如您所见，我们在循环之外总共有 5 个操作。

在第一个循环中，我们执行三个内部操作：检查 i 是否小于 n、打印“Hello World”和递增 i。

在第二个循环中，我们还有三个内部操作。

因此，我们需要的操作总数为：3n（第一个循环）+ 3n（第二个循环）+ 5（循环外的操作）。因此，所需的总步数为 6n+5（这是您的严格限制）。

正如我之前提到的，O(an +b)= n 因为一旦算法是线性的，当 n 非常大时，a 和 b 不会产生很大的影响。

因此，您的时间复杂度将变为：O(6n+5) =O(n)。

您可以对第二个示例使用相同的逻辑，记住两个嵌套循环采用 n² 而不是 n。

于 2013-04-29T13:26:54.170 回答
0

我会稍微修改约翰的回答。定义 n 是一个常数运算，定义整数 i 并将其赋值为 0 是 2 个常数运算。定义整数 j 并用 n 赋值是另外 2 个常量操作。在for循环、增量、打印语句中检查 i、j 的条件取决于 n，因此总数为 3n+3n+5，等于 6n+5。在这里，我们不能在执行期间跳过任何语句，因此它的平均案例运行时间也将是其最坏情况的运行时间，即 O(n)

于 2020-06-21T17:41:44.640 回答