当我在 DSA 讲座中学习时间复杂度时,我的脑海中突然出现了这个疑问。那么首先,是 O(log(n)) = O(log(n^n))?
如果是,O(log(n^n)) 属于什么类型的时间复杂度?是对数/二次/指数吗?
我尝试浏览其他 stackoverflow 文章,然后浏览 Chatgpt 和 Gemini。 Stackoverflow 可能没有这个问题,人工智能模型给出了非常明确的答案。期待人类智慧给出答案。
不,O(logu2061(n)) 与 O(logu2061(n^n)) 不同。这是因为 logu2061(n^n) 简化为 nlogu2061(n),并且 nlogu2061(n) 属于与 logu2061(n) 不同的时间复杂度类别。
O(logu2061(n^n)),相当于 O(nlogu2061(n)),称为线性时间。这是拟线性时间的特例,也称为对数线性时间。您可以在这里阅读更多相关信息:拟线性时间 - 维基百科。