gpt4 book ai didi

algorithm - 时间复杂度是多少?

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:12:50 25 4
gpt4 key购买 nike

以下函数的时间复杂度是多少?

    for(int i = 0; i < a.size; i++) {
for(int j = i; j < a.size; i++) {
//
}
}

我认为它小于 big O n^2,因为我们没有在第二个 for 循环中迭代所有元素。我相信时间复杂度是这样的:

n[ (n) + (n-1) + (n-2) + ... + (n-n) ]

但是当我解决这个公式时,结果是

n^2 - n + n^2 - 2n + n^2 - 3n + ... + n^2 - n^2

这似乎根本不正确。谁能确切地告诉我如何解决这个问题,以及我哪里错了。

最佳答案

O(n^2)。如果您考虑 i = a.size() - 1 的迭代,并且您向后工作(i = a.size() - 2 i = a.size - 3 等),您正在查看以下迭代次数总和,其中 n = a.size

1 + 2 + 3 + 4 + ... + n

这个级数的和是n(n+1)/2,也就是O(n^2)。请注意,大 O 表示法在应用于多项式函数时会忽略常量并采用最高的多项式幂。

关于algorithm - 时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23623309/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com