1.000.000 個の要素の配列があり、最初の文字が「A」であるかどうかなど、単純なものをチェックするためにそれらすべてを調べたとします。私の（ごくわずかな）理解からすると、複雑さが増し、O(n)Xの時間がかかります。チェックする別の IF (else if ではない) を追加すると、たとえば、最後の文字が「G」の場合、複雑さはどのように変化しますか? 複雑さと時間が 2 倍になりますか? のようO(2n)に2X？
さまざまなコマンドが実行しなければならない計算の数を考慮に入れることは避けたいと思います。たとえば、Len() では単純な char 比較よりも多くの計算が必要であることは理解していますが、IF で使用されるコマンドの複雑さは (ほぼ) 同じであるとしましょう。
漸近的複雑度 (big-O が使用するもの) は定数要素に依存しません。より具体的には、定数要素を関数に追加したり、関数から削除したりしても、同等のままになります (つまり、O(2n) = O(n))。 ）。
if ステートメントに一定の時間がかかると仮定すると、複雑さが一定の要素だけ追加されます。
「一定時間」とは、次のことを意味します。
したがって、各要素ごとに呼び出される 2 つの (一定時間の) if ステートメントは O(2n) になりますが、これは O(n) と等しくなります (実際には 2n ではない可能性があります。詳細については追加の注記を参照してください)。
詳細とより正式な定義については、ウィキペディアを参照してください。
注:一定の要素に依存しないことは別として、漸近的に小さい項 (n が大きくなっても小さいままである項)、たとえば O(n) = O(n + sqrt(n)) にも依存しません。そして、big-O は単なる上限であるため、O(n 9999 ) であると言うことも正しいでしょう (ただし、テスト / 試験ではおそらく 0 点が得られるでしょう)。
追記:一定の要因を無視しない場合の問題は、何を作業単位として分類するかということです。ここには標準的な定義はありません。1 つの方法は、最も時間がかかる操作を使用することですが、これを決定することは必ずしも簡単ではなく、常に特に正確であるとは限りません。また、異なるアルゴリズムの複雑さを一般的に比較することもできません。