algorithm - 以下方法的时间复杂度是多少？

Question

我试图了解如何检查时间复杂度，但我无法解决这个例子：

图片 ：

有人可以帮我解决它并逐步解释如何做吗？

标签： algorithmtime-complexitybig-o

Answer 1

算法循环直到 m 达到 0。在每次迭代中，m 要么减半（如果它是偶数），要么减 1（如果它是奇数）。如果算法在每次迭代中只将 m 减半，那么这将采取 log(m) 步骤（在复杂性的上下文中，log() 通常意味着以 2 为底）。然而，在我们的例子中，我们最多可能有两倍的迭代次数，也就是说，如果在偶数减半后得到一个奇数。这些奇数减 1，从而产生下一个偶数。

将步数加倍是一个常数因素，在使用 Big-O 表示法计算复杂度时不考虑该因素，因此复杂度保持在 O(log(n))。