「計算量」一覧

バブルソート バブルソート(bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば...

2分探索 二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。 出典: フリー百科事典『ウィキペディア（Wikipedia）』 ソートされている配列の探索は、線...

線形探索とは 線形探索（せんけいたんさく、英:linear search, sequential search）は、検索のアルゴリズムの一つ。リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。 ...

for ループを使う場合の計算量について考えます。 \( O(n) \) for ループの中に\( O(1) \)の処理がある場合は、\( O(n) \) になります。 for i=0 to N: # O(1) の処理 ...

参考 3 クラス P，N P, N P 完全，N P 困難 複雑性クラス 複雑性クラス（ふくざつせいクラス、英:Complexity class）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のよ...

アルゴリズムの計算量を考える時、主なオーダーのグラフは以下のようになります。 wikipedia より \( O(1) \) 定数 Constant、\( O ( \log n) \) 対数 Logarithmic、\( O (n) \) 線形 ...