38 cards · basic cards · AI-written, checked twice. Edit anything.
- ビッグO記法は何を測定しますか。
Show answer
入力サイズが増加するにつれて、アルゴリズムの実行時間や空間の必要量がどのように増加するかということ。- 計算量O(1)を定義してください。
Show answer
定数時間。入力サイズに関係なく実行時間が変わらない。- 計算量O(n)を定義してください。
Show answer
線形時間。実行時間は入力サイズnに比例して増加する。- 計算量O(log n)を定義してください。
Show answer
対数時間。実行時間は入力サイズの対数に応じて増加する。- 計算量O(n^2)を定義してください。
Show answer
二次時間。実行時間は入力サイズの2乗に応じて増加する。- 計算量O(n log n)を定義してください。
Show answer
線形対数時間。実行時間はnとnの対数の積になる。- 計算量O(2^n)を定義してください。
Show answer
指数時間。入力サイズが1増えるごとに実行時間が2倍になる。- 配列の要素にインデックスでアクセスする計算量は何ですか。
Show answer
O(1)、定数時間。- 未整列の配列である値を探索する計算量は何ですか。
Show answer
O(n)、線形時間。- 整列済み配列における二分探索の計算量は何ですか。
Show answer
O(log n)、対数時間。- 二分探索を使う前に配列について成り立っていなければならないことは何ですか。
Show answer
配列がソートされていること。- 配列の先頭に要素を挿入する計算量は何ですか。
Show answer
O(n)、線形時間。- 空き容量のある動的配列に要素を追加する計算量は何ですか。
Show answer
O(1)、償却定数時間。- ハッシュテーブルの探索の平均計算量は何ですか。
Show answer
良いハッシュ関数を使えばO(1)、定数時間。- クイックソートの平均計算量は何ですか。
Show answer
O(n log n)、線形対数時間。
FlashKeepers