在循环条件中，i<sqrtN（预先计算）或 i*i<N，在 C++ 中哪个更有效？

Question

假设对于给定的整数 N，我需要运行 N 次的循环平方根。

在 C++ 中，我可以通过这两种方式来做到这一点——

1)

long long sqrtN = std::sqrt(N);
for (long long i=1; i < sqrtN; i++) {
    // some piece of code
}

for (long long i=1; i * i < N; i++) {
    // some same piece of code
}

我发现 std::sqrt() 具有 O(logn) 复杂度。另外，我相信数字的乘法只是一个常数时间运算。

所以，感觉第2个版本更快。但是，对于非常大的 n 值，第二个版本中的恒定时间可能很重要。

因此，我不确定哪种方式更有效？

Answer 1

我发现 std::sqrt() 具有 O(logn) 复杂度。另外，我相信数字的乘法只是一个常数时间运算。

到现在为止还挺好。你错过了一个细节。第一次调用sqrt一次，第二次调用i*i在每次循环迭代中计算。因此它实际上是O(log n)vs O(sqrt(n))，即计算循环外的边界获胜，因为log n < sqrt(n)。

要真正知道什么更有效，渐近复杂性只能为您提供当您增加到n无穷大时会发生什么的第一个提示。对于实际情况，您应该查看编译器和配置文件的输出。

复杂性主要是理论上的兴趣，我再怎么强调也不为过。对于真正的代码，没有办法绕过分析和测量。O(N)算法胜过O(logN)算法的可能性不大，因为渐近复杂度完全忽略了任何常数因素。

PS：不要做过早的优化。编写代码以提高可读性，并将优化留给编译器。只有当您测量并发现计算循环边界花费了太多时间时，您才需要做一些事情。考虑到这i*i是一条指令，而您的循环体可能远不止于此（参见 Amdahls 定律）。