我对计算复杂度这个话题有些困惑。
我知道Big O以及如何计算循环的复杂性（也需要嵌套）。
假设我有一个程序，该程序具有从1到n运行的3个循环
for (int i=0;i<n;i++)
{
cout << i ;
}
现在，如果我运行的CPP代码包含3个for循环，是否需要3 * n的时间？
CPP编译器会同时运行所有3个循环，还是会一个接一个地执行？
我对这个话题很困惑。请帮忙！
如果代码包含多个n个复杂度循环，如何计算复杂度？
要了解Big-O表示法和渐进复杂性，至少采用半正式表示法可能会很有用。
考虑渐近时间复杂度的查找和上限问题，这是一个f(n)基于增长的函数n。
我们的帮助，让松散定义一个函数或算法f中存在O(g(n))（挑剔，O(g(n))是一组函数，因此f ∈ O(...)，而不是常用误用f(n) ∈ O(...)），如下所示：
如果函数
f是在O(g(n))，然后c · g(n)是上界f(n)，对于一些非负常数c，使得f(n) ≤ c · g(n)保持，对于足够大的n（即，n ≥ n0对于某一常数n0）。
因此，为了证明这一点f ∈ O(g(n))，我们需要找到一组(c, n0)满足以下条件的（非负）常数
f(n) ≤ c · g(n), for all n ≥ n0, (+)
让我们考虑一下您的实际问题
void foo(int n) {
for (int i = 0; i < n; ++i) { std::cout << i << "\n"; }
for (int i = 0; i < n; ++i) { std::cout << i << "\n"; }
for (int i = 0; i < n; ++i) { std::cout << i << "\n"; }
}
为了分析foo基于增长的渐近行为n，认为std::cout << i << "\n";是我们的基本运算。因此，基于此定义，foo包含3 * n基本运算，我们可以在foo数学上将其视为
f(n) = 3 * n.
现在，我们需要找到一个g(n)和一些组常数c和n0这样(+)成立。对于此特定分析，这几乎是微不足道的。f(n)如上所述插入(+)并让g(n) = n：
3 * n ≤ c · g(n), for all n ≥ n0, [let g(n) = n]
3 * n ≤ c · n, for all n ≥ n0, [choose c = 3]
3 * n ≤ 3 · n, for all n ≥ n0.
后者适用于任何有效条件n，我们可以任意选择n0 = 0。因此，根据上面对函数fin的定义O(g(n))，我们证明了fin O(n)。
显而易见的是，即使我们乘的循环中foo的时间多，只要这个倍数是恒定的（而不是依赖于n本身），我们总能找到常量的退化数c，并n0会履行(+)对g(n) = n，从而表明了函数f描述foo基于的基本运算的函数n是线性增长的上限。
现在，如果我运行的CPP代码包含3个for循环，是否需要3 * n的时间？
但是，必须理解，Big-O表示法描述了数学上描述的算法或例如基于基本操作的定义可以被描述为前者的以编程方式实现的函数的渐近行为的上限。但是，它没有提供准确的描述，您可能期望在什么运行时实现不同的功能。缓存局部性，并行性/向量化，编译器优化和硬件内在性，描述基本操作的不准确性只是使渐进复杂性与实际运行时间脱节的众多因素中的少数。链表数据结构就是一个很好的例子，其中的渐近分析不太可能提供良好的运行时性能视图（因为缓存局部性丢失，
对于算法的实际运行时，万一遇到瓶颈，使用产品代表的编译器和优化标志实际在目标硬件上进行测量是关键。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句