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