algorithm - 具有分配的恒定时间复杂度

Question

我对我的时间复杂度分析讲座的脚本完全感到困惑，我需要一些帮助。这是提供的讲座示例，我没有找到任何有用的答案。

monthly_installment = 50.00;
i = 1;
interest = 0.005;
assets = 100.00;

while i<n 
{
    assets = monthly_installment + assets + assets * interest;
    i = i + 1; 
}

对于此示例，我们有：while 外部的 4 个赋值，while 循环内的 (n + 1) 个比较，n*(2 add + 1 assignment + 1 mul)，n*(1 add + 1 assignment)。所以假设所有一起f（n）= 4 + 7n + 1，属于O（n）。

在练习中：

sum = 0;
i = n;
while i > 0 
{
   sum = sum + 1;
   i = floor(i/2);
}

在这种情况下，解决方案是 log(n)，O(log(n)) 的顺序。为什么在这种情况下，和赋值 n*(1 assignment + 1 add) = 2n 不是 O(n) 的顺序？这里有什么区别？在任何情况下，每个分配时间复杂度，即 a = b + c 常数 O(1)？

标签： algorithmtime-complexity

Answer 1

在情况 1 中，i 将是 1、2、3、...、n 并计算 n 次。在情况 2 中，我将是 floor(n / 2), floor(floor(n / 2) / 2), ..., 1，它们下降得更快。并非所有整数都将在此处计算。