6

このコードは Cracking the Coding インタビュー本からのものです。

public static boolean isUniqueChars2(String str) {
    boolean[] char_set = new boolean[256];
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i);
        if (char_set[val]) return false;
        char_set[val] = true;
    }
    return true;
}

そして、著者は次のように述べています。

時間の計算量は O(n) です。n は文字列の長さで、空間の計算量は O(n) です。

時間の計算量が O(n) であることは理解していますが、空間の計算量が O(n) になる方法がわかりません

私の考え: char_set は、入力 (str) のサイズに関係なく、サイズ 256 の配列のままです。"str" の長さが 100,000 であっても、char_set は 256 要素の配列のままです。したがって、この関数のメモリ要件は入力のサイズによって変化せず、一定の 256 のままであるため、スペースの複雑さは一定、つまり O(1) であると考えました。

私が間違っている場合、誰かが説明できますか（そして、なぜですか？）

どうもありがとう。

4

2 に答える 2

0

それはもう少し複雑だと思います：

文字が 2 回出現するまでの反復の最大回数は、文字列が構築されるアルファベットのサイズです。

このサイズが有限の場合、時間の計算量は O(1) です。そうでない場合、ブール配列は有限のサイズにすることはできません。したがって、空間の計算量は O(n) になります。

于 2013-03-13T22:00:11.003 に答える