时间复杂度 n(log(n)) 和 log(n^n)

Question

当我在 DSA 讲座中学习时间复杂度时，我的脑海中突然出现了这个疑问。那么首先，是 O(log(n)) = O(log(n^n))？

如果是，O(log(n^n)) 属于什么类型的时间复杂度？是对数/二次/指数吗？

我尝试浏览其他 stackoverflow 文章，然后浏览 Chatgpt 和 Gemini。 Stackoverflow 可能没有这个问题，人工智能模型给出了非常明确的答案。期待人类智慧给出答案。

Answer 1

不，O(logu2061(n)) 与 O(logu2061(n^n)) 不同。这是因为 logu2061(n^n) 简化为 nlogu2061(n)，并且 nlogu2061(n) 属于与 logu2061(n) 不同的时间复杂度类别。

O(logu2061(n^n))，相当于 O(nlogu2061(n))，称为线性时间。这是拟线性时间的特例，也称为对数线性时间。您可以在这里阅读更多相关信息：拟线性时间 - 维基百科。