daný Tu je kód pre konštrukciu stromu zpresuny a objednávanie. Nemôžem prísť na to, ako dospeli k časovej zložitosti O (n ^ 2). Nejaké nápady? Vidím, že hľadanie indexu v sekvencii inorder by bolo O (n), ako sa počíta zvyšok programu?
odpovede:
6 pre odpoveď č. 1Na O(N^2) zložitosť vyplýva zo skutočnosti, že pre každú položku v Preorder prechodu (z ktorej existuje N), musíte hľadať jeho oddiel v priečnom režime Inorder (opäť tam sú N z nich).
Hrubo povedané, tento algoritmus je možné považovať za umiestnenie uzlov na mriežku, kde priechod Inorder poskytuje súradnice x a prechádzka Preorder poskytuje súradnice y:
Vezmite príklad, ktorý dali, s nasledujúcimi priechodmi (Inorder then Preorder).
Inorder: DBEAFC
Preorder: ABDECF
Teraz je to mriežka, na ktorú sa kladú:
D B E A F C
A + + + A | |
| +--------------+ |
B|F + B | F |
+---------+ -----+
DE|C D E C
Teraz algoritmus potrebuje vedieť, kde v mriežke umiestniť každý uzol, ktorý robí jednoducho tým, že uzol v pozícii v mriežke, kde sú súradnice x a y rovnaké.
Vyzerá to, že veľkosť mriežky je v skutočnosti NlogN v tomto prípade, čo by malo za následok NlogN zložitosť prechodu siete (a tak NlogN časová zložitosť algoritmu) ale tento strom je vyvážený, V najhoršom prípade môže byť váš strom v skutočnosti prepojeným zoznamom.
Napr. zvážte tento strom, v ktorom sú predbežné a iniciálne putovanie rovnaké:
Inorder: DBEAFC
Preorder: DBEAFC
D B E A F C
D D | | | | |
-----+ | | | |
B B | | | |
-----+ | | |
E E | | |
-----+ | |
A A | |
-----+ |
F F |
-----+
C C
Toto je najhorší prípad, a vidíte, mriežka má N*N kontrolných pozícií. Takže v najhoršom prípade existuje N*N časovej zložitosti.
0 pre odpoveď č. 2
prechádzate celým preorder pole vnútri rekurzie av každom rámci zásobníka hľadáte číslo v inorder traversal array. tak O(N*N) = o(N^2).