Zenn
Open11

コンピュターサイエンス

JavaScript
Python
eidmeidm

プリミティブ型(int num = 100)とは違い文字列などは大きさが予測できないので、
変数に直接保存するのでは無く、メモリアドレスに保存され参照される。

cat にはオブジェクトのメモリアドレスが入る

let cat = new Car("mikeneko",6,"female" );
eidmeidm

配列

配列内の値取得の計算量 : O(1)
配列のコピーの計算量 : O(n)

eidmeidm

動的配列 n 個数の配列を持つ場合

  • 前方追加・削除の計算量

    • 追加 >> n >> O(n)
    • 削除 >> n - 1 ≒ n >> O(n)

  • 途中・追加削除の計算量

    • 追加 >> 0.5n ≒ n >> O(n)
    • 削除 >> 0.5n - 1 ≒ n >> O(n)

  • 末尾追加・削除

    • O(1) (収容可能サイズに余裕がある場合)
    • O(n) (論理サイズ = 収容可能サイズの場合)
eidmeidm

ハッシュは強力だが、n個のリストをハッシュマップにするのに O(n)の時間計算量・O(n)のメモリを必ず使うことに注意。
for 文をネストしないと解けないような問題は片方の要素をハッシュ化することでO(n * n)の時間計算をO(n)にできる可能性がある(2つ目の要素はハッシュ化された1つ目の要素にO(1)でアクセスできる)
1つ目の要素ハッシュ化にかかるのはO(n)、2つ目の要素をハッシュマップを使い解く
計算量でO(n) よって O(n) + O(n) ≒ O(2n) ≒ O(n)

eidmeidm

連結リストのポイント
xxx に次に参照してほしいデータをいれる

currrentNode.next = xxx
eidmeidm

用語のメモ

・preorderTraversal  前順操作 >  根、左、右
・inorderTraversal  間順操作 >  左、根、右
・postorderTraversal  間順操作 >  左、右、根