我正在阅读一些关于时间复杂性的信息，我很困惑，下面的时间复杂性是如何实现的，如果有一组特定的规则或方法来解决这个问题?
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)
对于给定的算法，时间复杂度或Big O是一种提供与给定输入大小n相关的"算法执行的总初等运算"的一些足够公平的估计的方法。
1型
假设你有一个这样的算法:
a=n+1;
b=a*n;
上面的代码中有2个基本运算，不管你的n有多大，对于上面的代码，计算机总是会执行2个运算，因为算法不依赖于输入的大小，所以上面代码的大0是O(1)。
2型
对于这个代码:
for(int i = 0; i < n; i++){
a=a+i;
}
我希望你理解O(n)中的大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²)但是没有，上述代码的时间复杂度为O(n^2)。为什么?因为我们试图知道对于给定的输入大小n，算法执行的基本操作的足够的计数，这将相对容易理解对于另一个人。这个逻辑,O (n) + O (n ^ 2) O (n ^ 2),或O (n ^ 2) + O (n ^ 3) + O (n ^ 4)成为O (n ^ 4) !
你可能会问:但是怎么做呢?为什么当我们把大0的低次幂加上大0的高次幂时，所有的大0的低次幂都变得微不足道，以至于当我们向另一个人描述算法的复杂性时，我们可以完全忽略它们(低次幂)?
我将尽力说明这种情况的原因: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)。
p。请原谅我的英语:)
在第一个示例中，数组有n个元素，您要遍历这些元素两次。第一次从索引0开始到i，第二次从索引n开始到0。为了化简，我们可以说它花了2n。在处理大0符号时，你应该记住我们关心的是边界:
因此，O(2n)=O(n)and 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。
我会稍微修改一下约翰的回答。定义n是一次常数运算，定义整数i并赋值给0是两次常数运算。定义整数j和赋值n是另外两个常量操作。检查循环中的i,j的条件，增量，打印语句取决于n，所以总数将是3n+3n+5，等于6n+5。这里我们不能在执行过程中跳过任何语句所以它的平均情况运行时间也将是它的最坏情况运行时间O(n)