オーダー記法 Part2 「オーダー記法と計算量の比較」 - shogonir blog

概要 この記事では「オーダー記法」と「計算量の比較」について説明します。 また、記事の内容は動画でも紹介していますので、よければ確認してください。 youtu.be オーダー記法とは オーダー記法は計算量を数学的に記述する方法です。 まずは具体例から紹介します。 例えば O(n) , O(log(n)) , O(n^2) のように表記します。 O() の中に数式を書くという決まりがあります。 Oは「程度」という意味のOrderという単語からきているそうです。 数式に使うのは、問題の入力に使う変数です。 例えばリスト探索であれば、 e , a , n が使えます。 線形探索と二分探索は n があればその計算量を表現できます。 ここで次のような問題について考えます。 問. 整列済みのリストを探索する場合、次の1と2のどちらが速いか？ 線形探索 二分探索 ここでは2つのアルゴリズムの最悪時間計算