Golang中这个算法的时间复杂度是多少？

Golang中这个算法的时间复杂度是多少？ myFunc函数的复杂度是多少？

func myFunc(n int) int {
    res := 0

    for i := n; i > 0; i /= 2 {
        for j := 0; j < i; j++ {
            res++
        }
    }

    return res
}

我认为是O(n)，我错了吗？

7 回复

外层循环运行 log2(n) 次。内层循环是 O(n)。所以整体是 O(n log n)？

更多关于Golang中这个算法的时间复杂度是多少？的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


我对此表示怀疑，因为操作总数将是 n * (1 + 1/2 + 1/4 + …) < 2 * n

如果它是O(n)，那么它返回的值永远不会大于你输入的n的一半。

但实际上，它返回的值要多得多。

不过我不确定这究竟是O(n log n)还是O(n²)。

对于算法复杂度而言，是否对 n 进行除法运算并不重要。任何常数因子都可以视为 1。

你运行了两个循环，一个内层循环和一个外层循环。外层循环的运行次数由参数决定，因此复杂度为 O(n*x)，其中 x 表示内层循环的复杂度。它的复杂度并非常数时间。所以你的算法不可能是 O(n)。

我认为是 O(n) 复杂度，因为第一次外循环运行时需要执行 n 次操作，第二次是 n/2 次，第三次是 n/4 次，依此类推。

因此通过累加 n (1 + 1/2 + 1/4 + 1/8 + …) ≤ n * 2，所以是 O(n) 复杂度。

我的理解有误吗？

NobbZ:

O(n²)

这绝对不是O(n²)，实际上O(n logn)是一个上界，因为以下代码（在内层循环中将i替换为n）具有这样的复杂度：

for i := n; i > 0; i /= 2 {
    for j := 0; j < n; j++ {
         res++
    }
}

外层循环是O(log n)（基本上与进行二分搜索相同），因此根据内层循环的不同，整个过程确实可能是O(n)。另一方面，如果我们只运行一次外层循环，那就等同于：

for j := 0; j < n; j++ {
    res++
}

这显然是O(n)，所以这是一个下界。这一点应该很清楚，因为内层循环不是常数时间，所以整个过程不可能是O(logn)。

那么让我们看看内层循环。它的复杂度取决于i，而i由外层循环动态改变。现在，我的复杂度计算有点（更确切地说是非常）生疏，但我的第一猜测是它实际上是O(n / logn)。为什么？因为循环确实执行了i次操作，考虑到外层循环，i从n开始，但这个n以对数方式递减。

所以，如果第二个复杂度是正确的，我们得到整个复杂度是O(logn * n / logn)，等同于O(n)。当然这种分离有点粗略，可能不是一个很好的解释，因为内层循环实际上是O(i)，我们需要考虑到i是n的函数，才能得出我想到的O(n / logn)复杂度。

现在，如果我们用n来实际计算操作次数，我认为John是正确的：我们开始执行n次操作，然后是n/2次，依此类推，使得它低于2*n而高于n，因此再次是O(n)。

虽然我在攻读学位时修了不少涉及计算机科学数学的课程，但正如我所说，那是几年前的事了，我并没有真正在白板上推导过这些。所以请对我的直觉持保留态度，如果你需要确定的话，请进行正确的数学计算。同时，请纠正我可能犯的任何错误。

这个算法的时间复杂度是 O(n)，你的判断是正确的。

让我详细分析一下：

func myFunc(n int) int {
    res := 0

    for i := n; i > 0; i /= 2 {        // 外层循环：log₂n 次
        for j := 0; j < i; j++ {       // 内层循环：i 次
            res++
        }
    }

    return res
}

循环执行次数分析：

  • 外层循环：i = n, n/2, n/4, …, 1，总共执行 log₂n + 1 次
  • 内层循环执行次数总和：n + n/2 + n/4 + … + 1

这是一个等比数列求和：

n + n/2 + n/4 + n/8 + ... + 1 = n × (1 + 1/2 + 1/4 + 1/8 + ...)

等比数列求和公式：S = a₁ × (1 - rᵏ)/(1 - r)，其中 a₁ = n, r = 1/2, k = log₂n + 1

S = n × (1 - (1/2)ᵏ) / (1 - 1/2) = n × (1 - 1/n) / (1/2) = 2n × (1 - 1/n) = 2n - 2

因此总操作次数是 2n - 2，时间复杂度为 O(n)。

验证示例：

func main() {
    // 测试 n=8
    // 循环过程：i=8(j=0-7), i=4(j=0-3), i=2(j=0-1), i=1(j=0)
    // 总操作次数：8+4+2+1=15，符合 2×8-2=14（近似）
    fmt.Println(myFunc(8)) // 输出：15
    
    // 测试 n=16  
    // 16+8+4+2+1=31，符合 2×16-2=30（近似）
    fmt.Println(myFunc(16)) // 输出：31
}

虽然外层循环是 O(log n)，但由于内层循环的迭代次数呈几何级数递减，总操作次数被限制在 O(n) 范围内。

回到顶部