计算两个函数的时间复杂度

Question

O(n) 和 O(Log n) 的时间复杂度有什么区别。假设我有一个函数，它的时间复杂度为 O(Log n)，空间复杂度为 n。

如果我必须计算加法两个时间复杂度为

的函数，时间复杂度是多少？

• Log n 和 Log n
• 记录 n 和 n
• n 和 n

Answer 1

取n的最高“次方”

• Log n 和 Log n -> Log n
• 记录 n 和 n -> n
• n 和 n -> n

不要理会常数项。我们只对缩放行为感兴趣，即

当我们有 n 倍时，整个空间或时间会发生什么变化？

如果所需的空间或时间增加了相同的因子，则为O(n)。

如果对于输入大小的每个比例因子，它上升一个常数 additive 步长，我们说它是 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

不，这不像计算对数。但即使是，你做错了算术。

你问的是一个涉及 two 必须一个接一个发生的子流程的流程。所以所花的时间是加法，而不是乘法。

你要计算的是

log N + log N =  2 log N

但对于 O 表示法，我们忽略

2

，只将结果写为 O(log N)。