0Pricing
Competitive Programming Academy · レッスン

Big-O で演算回数を数える

定数時間から二次時間までを平易に学びます

「Big-O で演算回数を数える」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

操作回数を数える理由

コンテストでは速度が勝敗を分けます。コードの実行時間を測る代わりに、必要な手順の数を見積もります。この見積もりが時間計算量です。🚀

Big-O を知る

Big-Oは、入力サイズ n が大きくなるにつれて操作回数がどのように増えるかを表します。細かな要素は無視し、支配的な傾向に注目します。

定数時間 O(1)

処理量が n にまったく依存しない場合、それは O(1) です。リストの要素を1つ読み込む処理や1回の加算は、常に同じ時間で完了します。

x = arr[0]
y = a + b

線形時間 O(n)

n 個の要素を1回走査する単純なループは O(n) です。入力を2倍にすると、処理量もおよそ2倍になります。日常的に最もよく使う計算量です。

for x in arr:
    total += x

二次時間 O(n の 2 乗)

n 個の要素に対するループの中に、もう1つループがあると O(n^2) です。n = 1000 なら100万ステップになり、ここから急速に増加します。

for i in range(n):
    for j in range(n):
        check(i, j)

対数時間 O(log n)

各ステップで問題の大きさを半分にすると、O(log n) になります。二分探索なら、10億個の要素にも約30ステップで到達できます。✨

増加率の階段

速い順から遅い順に並べると、一般的な計算量の順序は O(1)、O(log n)、O(n)、O(n log n)、O(n^2) です。上にあるほど、入力が増えても効率よく処理できます。

定数倍を無視する

Big-O では定数倍を無視するため、O(2n) は単に O(n) です。2回走査しても増加は線形なので、倍数によって計算量のクラスは変わりません。

最大の項だけを残す

項を足し合わせる場合は、最も速く増加する項だけを考えます。O(n^2 + n) は O(n^2) になります。n が大きくなると n^2 が n を圧倒するためです。

連続ループと入れ子ループ

2つのループを続けて実行すると、合計は O(n + n) = O(n) です。2つのループを入れ子にすると O(n^2) になります。どちらになるかは、ループの構造から判断できます。

最悪ケースから考える

コンテストでは最も難しいテストケースで判定されるため、最悪ケースについて考えます。途中で早期終了すると仮定せず、ループが最後まで実行されると考えてください。

確認問題

Big-O の感覚を試してみましょう。

復習

コードを、O(1)、O(n)、O(n^2)、O(log n) といった増加率として読めるようになりました。定数倍を捨て、最大の項を残し、最悪ケースを考えてください。🎯

よくある質問

「Big-O で演算回数を数える」レッスンは無料ですか？

はい。「Big-O で演算回数を数える」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「Big-O で演算回数を数える」で何を学びますか？

定数時間から二次時間までを平易に学びます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。

「Big-O で演算回数を数える」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. Big-O で演算回数を数える
  2. 10^8 の経験則
  3. 制約を読み、計算量を選ぶ
  4. TLE が起きる理由と見つけ方
← Competitive Programming Academyに戻る