min*_*ino 0 sorting algorithm performance complexity-theory time-complexity
我正在阅读一些有关时间复杂度的信息，我对如何实现以下时间复杂度以及是否有一套特定的规则或方法来解决这一问题感到非常困惑。
1）
Input: int n
for(int i = 0; i < n; i++){
print("Hello World, ");
}
for(int j = n; j > 0; j--){
print("Hello World");
}
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;
Joh*_*hn 5
在第一个示例中，数组有 n 个元素，您将遍历这些元素两次。第一次从索引 0 开始直到 i，第二次从索引 n 开始到 0。因此，为了简化这一点，我们可以说它花了 2n。在处理 Big O 表示法时，您应该记住我们关心的是边界：
\n\n结果，O(2n)=O(n)\n 且 O(an+b)=O(n)
\n\nInput: int n // operation 1\n for(int i = 0; i < n; i++){ // operation 2\n print("Hello World, "); // Operation 3 \n }\nfor(int j = n; j > 0; j--) // Operation 4\n {\n print("Hello World"); //Operation 5\n } \n正如你所看到的，我们在循环之外总共有 5 个操作。
\n\n在第一个循环中，我们执行三个内部操作：检查 i 是否小于 n、打印“Hello World”以及递增 i 。
\n\n在第二个循环内，我们还有三个内部操作。
\n\n因此，我们需要的操作总数是：3n（第一个循环）+ 3n（第二个循环）+ 5（循环外的操作）。因此，所需的总步数为 6n+5（这是您的紧界）。
\n\n正如我之前提到的，O( an +b )= n，因为一旦算法是线性的，当 n 很大时，a 和 b 不会产生很大的影响。
\n\n所以，你的时间复杂度将变成：O(6n+5) =O(n)。
\n\n您可以对第二个示例使用相同的逻辑，请记住两个嵌套循环采用 n\xc2\xb2 而不是 n。
\n对于给定的算法，时间复杂度或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;
}
}
如您所见，循环1为O（n），循环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。请原谅我的英语:)