同じforループ内の比較回数は時間の複雑さに影響しますか？

Question

サンプルエクササイズでは、配列内のすべての要素が同じかどうかを確認しました。この質問は、これを行う最も効率的な方法ではありません。むしろ、これらの2つのソリューションについてです。

for(var i=0; i < set.length-1; i++) 
    { 
    if (set[i] != set[i+1]) // could have compared all elements to the firstelement instead of switching 
    { 
    isTrue=false; 
    } 

    } 

上記のアルゴリズムは、各インデックスとその後のインデックスを比較します。

var firstIndex=set[0]; 
for(var i=0; i < set.length-1; i++) 
{ 
    if(set[i] != firstIndex) 
    { 
     isTrue=false; 
    } 
} 

このアルゴリズムでは、現在のインデックスと最初のインデックスを比較しますが、これらのアルゴリズムは少なくともO（N）であるが。比較の違いが時間/空間の複雑さに影響しますか？

Answer 1

まあ、それらの両方のための

時間の複雑さがO(n)だろう明確な物事をすることができます。スペースの複雑さはO(1)です。

配列インデックスアクセスなどは、Big-Oタイムの複雑さに影響しません。

これらのアルゴリズムは少なくともO（N）ですが。

これは少なくともO(n)です。

あなたは条件が `I

if(set[i] != firstIndex) 
{ 
    isTrue=false; 
    break; 
} 

Answer 2

スペースの複雑さ：余分な変数/データ構造を使用していないため、変更はありません（2番目のスニペットのfirstIndexは一定のスペースを取るため考慮されていません）。

時間複雑度：ほとんど変化しません。どちらのスニペットでも、1回の比較を行っていますが、最初のスニペットは配列のアクセスが直接的な可変アクセスと比較して遅いため、少し遅くなります。