以下のコードの計算量を評価します。N 個のノードを順に見ていく処理を行っていますので、計算量は O(N) と評価できます。

void printList() {
    Node* cur = nil->next;
    for (; cur != nil; cur = cur->next) {
        cout << cur->name << " -> ";
    }
    cout << endl;
}

以下のコードにおいて、get(i) (head からスタートして i 番目の要素を取得する関数) では、それぞれ i 個のノードを見ていくことになります。よって以下のコードの計算時間は

　　1 + 2 + ... + N = N (N + 1) / 2

に比例しますので、計算量は O(N^2) と評価できます。

なおこのコードは、結局 N 個のノードを順に見ていくものとなっていますが、8.1 のように処理するのに比べて計算量が悪化していることが見て取れます。

for (int i = 0; i < N; ++i) {
    cout << get(i) << endl;
}

連結リストのサイズを表す変数 (ここでは s とします) を用意します。連結リストの初期化時において、s = 0; と初期化しておきます。

そして、連結リストに新たな要素が挿入されるときには ++s; と s をインクリメントして、連結リスト中の要素が削除されるときには --s; と s をデクリメントします。

このとき、変数 s は常に「連結リストのサイズ」を表すようになります。

単方向連結リストにおいて、特定のノード v を削除するためには、v の直前のノード p を特定する必要があります。もし O(N) の計算量を消費してよいならば、N 個のノードを順に見ていき、

　　p->next = v

となるようなノード p を線形探索しましょう。そうすれば、ノード v を削除する操作は次のように実現できます。

// 削除するノード v の直前のノード p が見つかったことを全体にする
void erase(Node *v, Node *p) {
    if (v == nil) return;  // v が番兵時は何もしない
    p->next = v->next;
    delete v;
}

ハッシュテーブル (C++ では std::unordered_set 型、Python では set 型) を活用します。まず、N 個の相異なる整数 a[0], a[1], ..., a[N-1] をハッシュテーブル (H とします) に挿入しましょう。この作業は平均的に O(N) の計算量で実現できます。

次に各 i (= 0, 1, ..., M-1) に対して、b[j] が H に含まれるかどうかを調べていきます。a と b とで共通する整数の個数を表す変数 counter (0 で初期化します)　を用意しておき、b[j] が H に含まれるならば、counter++; というように、変数 counter をインクリメントします。この作業は平均的に O(M) の計算量で実現できます。

そして最後に変数 counter の値を出力します。全体として平均的に O(N + M) の計算量で実現できます。

ハッシュテーブルによって実装された連想配列 (C++ では std::unordered_map 型、Python では dict 型) を活用します。N 個の整数 a[0], a[1], ..., a[N-1] に対して、次のような連想配列を作成しましょう。平均的に O(N) の計算量で作成できます。

D[v] ← 数列 a[0], a[1], ..., a[N-1] の中に、整数 v が含まれている個数

次に、答えを表す変数 result (0 で初期化します) を用意します。そして各 i (= 0, 1, ..., M-1) に対して、result += D[b[j]]; というように答えに加算していきます。この作業は平均的に O(M) の計算量で実現できます。

そして最後に変数 result の値を出力します。全体として平均的に O(N + M) の計算量で実現できます。

まず問 8.6 と同様に、N 個の整数 a[0], a[1], ..., a[N-1] に対して、次のような連想配列を作成しましょう。平均的に O(N) の計算量で作成できます。

D[v] ← 数列 a[0], a[1], ..., a[N-1] の中に、整数 v が含まれているかどうかを表すブール値 (True / False)

そして、各 i (= 0, 1, ..., M-1) に対して、D[K - b[i]] が True となることがあるかどうかを判定します。この作業は平均的に O(M) の計算量で実現できます。

全体として平均的に O(N + M) の計算量で実現できます。