big-o - 関数の内部に 2 つの for ループがある (ネストされていない) 場合、bigOh は関数全体で O(n) のままですか?

Question

関数内に異なるループがあっても、BigOh が乗算されることはありませんよね?

例：

function() {
    for(int i = 0; i < n; i++) {
        //logic here
    }

    for(int i = 0; i < n; i++) {
        //logic here
    }
}

Answer 1

これはかなりよく議論されています（つまり、一般的なリファレンス）が、はい、あなたは正しいです。あなたの質問にある関数はO（n）です。

技術的には O(2n) が O(n) に還元されます

Answer 2

はい、O(2n) である O(n+n) があるため、まだ O(n) ですが、無視できる効果があるため、2 は無視できます。しかし、もしあなたが持っていたら

for (...){
  for(...){
    //code here
  }
}

次に、O(n^2) になります。