gpt4 book ai didi

c++ - 大 O 符号混淆(C++)

转载 作者:行者123 更新时间:2023-11-28 05:07:05 26 4
gpt4 key购买 nike

int f(const std::vector<int>& v) {      
int result = 0;
for (int i = 0; i < v.size(); ++i) { O(N)
for (int j = v.size(); j >= 0; j -= 2) { O(N/2)
result += v.at(i) * j;
}
}
return result;
}

内部的 for 循环是 O(N/2),但是我想知道这是为什么

例如,如果v.size()为10,那么

10 >= 0 ✓

8 >= 0 ✓

6 >= 0 ✓

4 >= 0 ✓

2>= 0 ✓

0 >= 0 ✓

-2 失败

内部 for 循环可以执行 6 次,输入大小为 10

我错过了什么?

编辑* 我知道只考虑最高震级。这个问题更多的是想出原来的 O(N/2 + 1)

最佳答案

复杂性为您提供了一种方法来评估完成特定大小的输入所需的时间量级,而不是它执行的准确时间。

因此,在处理复杂度时,应该只考虑最高量级,不考虑常数乘数:

O(N/2 + 1) = O(N/2) = O(N)

关于c++ - 大 O 符号混淆(C++),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44448608/

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