1

コード：

var PhoneNumbers = {
    "J Smith": 7125551212,
    "A Johnson": 4023331212
}

alert(PhoneNumbers["J Smith"]); // 7125551212

このルックアップの速度は O(1) です。速度が O(1) よりも遅くなる深さは?

例えば：

var PhoneNumbers = {
    "J Smith": {
         age: 40,
         phoneNumber: 7125551212
    },
    "A Johnson": {
         age: 40,
         phoneNumber: 7125551212
    }
}

alert(PhoneNumbers["J Smith"]["phoneNumber"]); // 7125551212

2 番目の例の速度は O(1) より遅いですか?

4

1 に答える 1

2

ネストされたディクショナリ ルックアップの複雑さは O(N) です。ここで、N はネストの深さです。

特定のルックアップ操作 (固定オブジェクト、固定キー)の複雑さは一定です (つまり、O(1)): 常に同じ時間がかかります。

少なくとも「典型的な」ケースでは、個々のルックアップは O(1) にある必要があります。ディクショナリは通常、ハッシュ テーブルとして実装され、すべてのキーが同じハッシュ値を持つ場合、理論的には O(N) (N はディクショナリ内のキーの数) に低下する可能性があります。

于 2013-05-31T18:04:08.487 に答える