大O表示法用于两个非嵌套循环 [英] Big O Notation for two non-nested loops

问题描述

对于两个未嵌套的for循环，Big O表示法是什么?

示例:

for(int i=0; i<n; i++){
   System.out.println(i);
}

for(int j=0; j<n; j++){
   System.out.println(j);
}

解决方案

线性

O(n) + O(n) = 2*O(n) = O(n)

您有多少个非嵌套循环(如果该数目是一个常数，并且不依赖于n)并不重要，复杂度将是线性的，并且将等于循环中的最大迭代次数. /p>

What would the Big O notation be for two for loops that aren't nested?

Example:

for(int i=0; i<n; i++){
   System.out.println(i);
}

for(int j=0; j<n; j++){
   System.out.println(j);
}

解决方案

Linear

O(n) + O(n) = 2*O(n) = O(n)

It does not matter how many non nested loops do you have (if this number is a constant and does not depends on n) the complexity would be linear and would equal to the maximum number of iterations in the loop.

这篇关于大O表示法用于两个非嵌套循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！