tree - 大 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 的情况。

n ^{2 log n} = 1024 ^{2 * log 1024} =1024 ²⁰ =1606938044258990275541962092341162602522202993782792835301376。

其中 n ^1.01 =1024 ^1.01 =1097.5