我需要计算以下代码的时间复杂度:
for (let i = 1; i < n; i = i * 2) { console.log(i); }
请解释如何在日志中计算复杂性
mrfwxfqh1#
在不涉及数学复杂性(可以在维基百科上找到)的情况下,完全用外行的话来说,只要每次迭代减少一定百分比的工作量,就可以达到o(logn)。在循环示例中,反向运行它(从n到零),每一步将剩余工作量减少一半(50%)。然而, i = i * 1.4 也将是o(logn)。
i = i * 1.4
1条答案
按热度按时间mrfwxfqh1#
在不涉及数学复杂性(可以在维基百科上找到)的情况下,完全用外行的话来说,只要每次迭代减少一定百分比的工作量,就可以达到o(logn)。
在循环示例中,反向运行它(从n到零),每一步将剩余工作量减少一半(50%)。
然而,
i = i * 1.4
也将是o(logn)。