Array

Array には Array List と Linked List がある
Array Listはメモリ上に連続的に存在しているためindexさえあればアクセスできる
Linked List は Nodeを元に作成されており、indexでアクセスするためにはheadから辿る必要があり、O(n)かかる。

pythonのpalindromeの証明、n == n[::1] って頭良すぎやろ

snowindy 2022/11/28に更新

recursive

再帰は人間にも分かりづらいが stack を使うと分かりやすい
computerがrecursive function を実行するときに、現在の関数のローカル変数や関数のどこにいるのかを知る必要がある。これは runtime stack stack frame と呼ばれている。
Pythonなどではstack frame がでかく、n=1000くらいで最大に達する。よって安易に再帰はするべきでない

snowindy 2022/11/30に更新

Linked List

Singly Linked List (単連結リスト）。普通の配列に比べて扱いにく過ぎだろ(readがO(N)なので)と思ったが、
連結リストは挿入が簡単というメリットがある。挿入する操作がnextを付け替えるだけで実装できるからだ。配列の場合は、挿入後にあるカラムを全部移動させなければならない。

余談

Palindrome Linked List の Anwer3の In-place algorithm が天才的。応用できそう
in-placeとは: https://ja.wikipedia.org/wiki/In-placeアルゴリズム#:~:text=in-placeアルゴリズムとは,から来る用語である。
ソートの話に関係しそうですね。

snowindy 2022/12/10

Hash Map

hash = map = hashmap = dict. 呼び方は何でもあり。
基本的にhashmapは特定のアルゴリズムを用いてキーを探索しているためソートはしてくれない。けどなぜかPythonのdictはしてくれてる。なんで？
追記順ならいうてnextかなんか実装すれば順番通りにしてもO(1)ですむのかな？未だ謎は多い

snowindy 2022/12/10に更新

Heap

英語で「山積み」という意味。データ構造のheapと、動的メモリ領域のheapがあるのでややこしいが、実はヒープ領域はヒープ構造で実装されているとかいないとか。

ヒープ木構造

インデックスは深さ探索。
親ノード(k)は子ノード（2k, 2k+1）よりも小さくなければならない。(k=1,2,3..)
ヒープ作成(build_min_heap)の最悪計算量はO(n), min_heapify(ヒープ構造を作る上で、上のルールを守るためにノードを入れ替える作業)の最悪計算量はO(logn)である。

ヒープ領域

未使用ノード、使用中ノードに分かれる。最初は一つの大きい未使用ノードで、mallocやnewでメモリ確保されると、未使用ノードから必要分切り離して与える。free or deleteされるとまた未使用ノードに戻るが、動的に削除されるのでフラグメンテーションが発生する。これをガベージコレクションでまとめないと再利用しにくい。