O(n)和O(Log n)的时间复杂度有什么区别?假设我有一个函数，它的时间复杂度为O(Log n)，空间复杂度为n。
如果我必须计算两个函数的加法，时间复杂度为:
- Log n和Log n
- Log n和n
- n和n
取最高的"幂";n
- Log n和Log n ->o (Log n)
- Log n和n ->n
- n和n ->n
不要考虑常数项。我们只对缩放行为感兴趣，即
当我们有n倍以上时，整个空间或时间会发生什么?
如果所需的空间或时间增加相同的因子，则为O(n)。
如果输入大小的每一个比例因子都增加一个恒定的加性步，我们说它是O(log N)。例如，对于大小为1,10,100的大小，时间可能是4秒，4.5秒，5秒。然后每增加10倍数据就增加0.5秒。
如果它增加了这个因子的平方，它就是O(n^2)
不完全像计算对数
你提出了一个很好的问题:
会不会是Log n * Log n ->Log ^2(n) = Log (n)×log(n) = Log (n)^2?
我正在看这个答案quora.com/Difference-between-log-2-n-log-log-n-and-log-n-2 qr.ae/pr3wPd
这是错误的算术。
您正在询问涉及两个子过程的过程，这些子过程必须一个接一个地发生。因此，所花费的时间是加法，而不是乘法。
你要计算的是
log N + log N = 2 log N
但是对于0符号，我们忽略2，只将结果写成O(log N)。
当你有一个循环调用另一个循环时，你将O()
中的东西相乘正如@Support Ukraine在评论中指出的:
如果一个O(log n)的算法(在其最内层循环中)调用另一个也是O(log n)的算法，则得到的复杂度为O((log n) ^2)。
当你有两个相加的步骤(即不是相乘的)时，你取最高的"幂";n
如果你的过程涉及到做一个O(N)的事情，然后一旦它完成了，做一个O(log N)的事情，那么总体结果是O(N)。
这是因为一旦N变大，N的增长速度会比log N快得多。
快速总结:把它想象成"正比于">
当你说某物与另一物成正比时，你并不真正关心任何常数项。
假设人们吃的量与他们的体重成正比。你可以这样说，而不用说明我们谈论的是多少顿饭、多少天或多少年。持续时间会影响比例常数，但不会影响"所吃食物的成本"的概念。与"体重"成正比。
例如，如果你在货币之间切换，或者增加税收，比例常数改变，但比例保持不变。