computational-complexity

計算量 (computational-complexity)

計算量は、入力サイズが増えたときに必要な計算時間や手数、メモリ使用量がどのように増えるかを扱う考え方。動画では、辞書を1ページずつ探すオーダーNと、半分ずつ絞るオーダーlogNの違いを使って説明される。

量子コンピュータの「速さ」は、CPU のクロックを上げるような物理的高速化ではなく、この計算量のオーダーを改善できるかどうかにある。グローバーのアルゴリズムやショアのアルゴリズムは、その代表例として扱われる。