是 2^(log n) = O(log(n)) 吗？
Is 2^(log n) = O(log(n))?
这两个相等吗？我在某处读到 O(2lg n) = O(n)。根据这一观察，我猜答案是否定的，但我不完全确定。如果有任何帮助，我将不胜感激。
首先，O(2log(n)) 不等于 O(n)。
要使用大 O 表示法，您会找到一个表示算法复杂度的函数，然后您会在该函数中找到具有最大增长率的项。最后，您将尽可能消除任何常数因子。
例如假设您的算法迭代 4n^2 + 5n + 1 次，其中 n 是输入的大小。首先，您将采用增长率最高的项，在本例中为 4n^2，然后删除任何常数因子，留下 O(n^2) 复杂度。
在你的例子中，O(2log(n))可以简化为O(log(n))
现在回答你的问题。
在计算机科学中，除非另有说明，否则您通常可以假设 log(n) 实际上表示 n 的对数，以 2 为底。
这意味着，使用对数定律，2^log(n) 可以简化为 O(n)
证明：
y = 2^log(n)
log(y) = log(2^log(n))
log(y) = log(n) * log(2) [Log(2) = 1 since we are talking about base 2 here]
log(y) = log(n)
y = n
这两个相等吗？我在某处读到 O(2lg n) = O(n)。根据这一观察，我猜答案是否定的，但我不完全确定。如果有任何帮助，我将不胜感激。
首先，O(2log(n)) 不等于 O(n)。
要使用大 O 表示法，您会找到一个表示算法复杂度的函数，然后您会在该函数中找到具有最大增长率的项。最后，您将尽可能消除任何常数因子。
例如假设您的算法迭代 4n^2 + 5n + 1 次，其中 n 是输入的大小。首先，您将采用增长率最高的项，在本例中为 4n^2，然后删除任何常数因子，留下 O(n^2) 复杂度。
在你的例子中，O(2log(n))可以简化为O(log(n))
现在回答你的问题。
在计算机科学中，除非另有说明，否则您通常可以假设 log(n) 实际上表示 n 的对数，以 2 为底。
这意味着，使用对数定律，2^log(n) 可以简化为 O(n)
证明：
y = 2^log(n)
log(y) = log(2^log(n))
log(y) = log(n) * log(2) [Log(2) = 1 since we are talking about base 2 here]
log(y) = log(n)
y = n