这两个是平等的吗？我在某处读到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