HTML DOMルックアップの時間の複雑さは何ですか

クレイジーな最適化がないと仮定します（私はChromeを見ています）。HTML DOMルックアップの時間の複雑さは何ですか

私は生の、厄介な、壊れていない、つまり、v6のjavascriptの、それを修正していない、ということについて話しています。

下限ビーイング：対

document.getElementById()

：ハッシュテーブルはのための完全なデータ構造であるとして

document.getElementsByTagName('div') lookup.

IE 6用に最適化している場合は、「ain't-broke」の部分を再考することをお勧めします。 – robrich

@robrich私は何も最適化していません。ちょっと興味があるんだけど。私はie6が 'aint-broke'の背後にある皮肉を表すと思った。たぶん私は明確にするためにそれを「引用」するべきです。 –

getElementByIdは、安全に、現代のブラウザでO(1)あると想定することができますid =>要素マッピング。任意の最適化なし

は、任意の単純クエリ - それはCSSセレクタ、ID検索、クラスまたはタグ名の検索が可能 - すべての要素の上で1つの反復が十分に常にあるので、O(n)よりも悪いではありません。

しかし、良いブラウザでは、タグマーム=>要素マッピングがあると期待しているので、getElementsByTagNameもO(1)になります。

2012-05-04 06:54:17 ThiefMaster

最終的な要素があなたが探しているものである可能性があるので、最適化されたgetElementsByTagNameは最適な場合でもO（n）でなければなりません –

これは、書き込み速度が最大になるように、？少しメモリを増やすのではないでしょうか？ –

これらのマッピングのメモリ使用量は無関係です。それは、例えば、メモリにキャッシュされた単一の画像（ウェブサイト上の背景画像など）。 – ThiefMaster

答えて