[データ構造] Pythonでの連結リスト
連結リストを Python で実装します。 ノードのクラス 連結リストのそれぞれのノードは、自身のデータと、次のノードを指すリンクを持ちます。 class Node(object): def __init__(self, data...
[データ構造] 連結リスト
連結リスト 連結リスト（れんけつリスト、英語:Linked list）は、最も基本的なデータ構造の1つであり、他のデータ構造の実装に使われる。リンクリスト、リンクトリストとも表記される。 出典: フリー百科事典『ウィキペディア（Wikipedia）』...
[データ構造] Pythonでの配列
Python には配列はビルトインとしては存在しません。 配列ではなく、同一の型でなければならないという配列の制約を取り払った「リスト」と言われるデータ構造が使われます。 少しややこしいですが、Python のリストは一般的な "Linked L...
[データ構造] 配列
配列 複数の要素（値）の集合を格納・管理するのに用いられるデータ構造が配列である。数学のベクトルおよび行列に近い概念であり、実際にベクトルおよび行列をプログラム上で表現する場合に配列が使われることが多い。同様に複数要素の集合を管理するデータ構造（コレ...
[データ構造] データ構造とADT
データ構造 データ構造（データこうぞう、英: data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 出典: フリー百科事典『ウィキペディア（Wikipedi...
[計算量をざっくり理解 ] バブルソートの計算量
バブルソート バブルソート(bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば...
[計算量をざっくり理解] 2分探索の計算量
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）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のよ...