計算量
計算量(complexity)
そのプログラムがどれくらい速いかを大雑把に表す指標
入力サイズの増加に対して、実行時間がどれくらいの割合で増加するかを表す指標
問題を解決するためのアルゴリズムをコンピュータで処理させようとするとき、その処理に必要な資源 (計算時間, 記憶容量など)の尺度
書くときは$ O(n) のような表記で書かれる
アルゴリズムを計算量で表すと
二分探索だと$ O(\log n)
バブルソートだと $ O(n^2)
コンピュータが特定の手順に従って与えられた問題を解く際に必要とする記憶領域の容量
アルゴリズムの実行にどれだけ記憶領域 (メモリ) が必要かの量
プログラムの実行に必要な記憶領域
プログラムの実行に必要な時間
アルゴリズムの実行にどれだけ時間がかかるかという尺度に基づいて評価する時間計算量
もっと細かいもの
一番よいときの計算量を最良時間計算量 (best-case time complexity)
運が悪く最悪の条件の場合の計算量は最悪時間計算量 (worst-case time complexity)
確認用
Q. 計算量
Q. 領域計算量
Q. 時間計算量
Q. 多項式
Q. $ O(n \log n), O(n) どちらが計算量が大きい?
Q. $ O(\log n), O(n) どちらが計算量が大きい?
Q. 指数オーダーで解ける問題と言ったときの計算量の例は?
Q. 線形探索法の計算量はいくら？
Q. 二分探索法の計算量はいくら？
関連
参考
メモ