回答編集履歴
1
全体のループ回数も考慮しないといけない
test
CHANGED
|
@@ -42,4 +42,4 @@
|
|
|
42
42
|
```
|
|
43
43
|
念のため説明しますが、このコード全体がO(n)というわけではありません。O(n)なのは、22～35行目のループです。コード全体だとクエリがQ個なのでO(Qn)です。
|
|
44
44
|
|
|
45
|
-
さて、22行目から35行目のループを考えたときに、最も多くの回数実行されるコードは、一番内側のループ内(25～26行目)となります。一番内側のループで注目すべきは、26行目の`++right`になります。22～35行目のループ内を見ると分かりますが、`right`はループ内で増える一方で、減ることは一切ありません。また、24行目のループ継続条件に`right < n`が含まれるので、`right`が`n`まで増えると、一番内側のループは実行されません。その条件下で、26行目の`++right`が最大何回実行されうるか考えると、n回までしか実行できないことが分かります。最も多くの回数実行される一番内側のループ内のコードが最大n回までしか実行されない
|
|
45
|
+
さて、22行目から35行目のループを考えたときに、最も多くの回数実行されるコードは、一番内側のループ内(25～26行目)となります。一番内側のループで注目すべきは、26行目の`++right`になります。22～35行目のループ内を見ると分かりますが、`right`はループ内で増える一方で、減ることは一切ありません。また、24行目のループ継続条件に`right < n`が含まれるので、`right`が`n`まで増えると、一番内側のループは実行されません。その条件下で、26行目の`++right`が最大何回実行されうるか考えると、n回までしか実行できないことが分かります。最も多くの回数実行される一番内側のループ内のコードが最大n回までしか実行されないことと、22～35行目のループ自体も最大n回までしか実行されないことから、O(n)であるということができます。
|