大O問題：一般樹操作和相對複雜性

Question

這實際上並不是家庭作業，但我需要理解這些概念。

插入，查找和 在一般樹中刪除操作的最壞情況Big-O性能是什麼？這是爲什麼？

我不知道如何接近那個，因爲在一般樹上沒有收縮。

它生長快，爲O（n^2 *的log（n）），或者爲O（n^1.01）

Answer 1

爲O（n ^{2爲log N}）增長爲O快得多得多（ n ^1.01）。我假設對數的底數是2，就像許多樹算法一樣。

例如考慮n = 1024時的情況。

Ñ^{2爲log N} = 1024 ^{2 *登錄1024} = 1024 = 1606938044258990275541962092341162602522202993782792835301376。

凡正^1.01 = 1024 ^1.01 = 1097.5