c++ - 是否定义为 C++ 标准算法提供空范围？

Question

从 my previous question 开始，我们能否证明标准允许我们将空范围传递给标准算法？

第 24.1/7 段将“空范围”定义为范围 [i,i)(其中 i 有效)，并且 i 本身似乎是“可达的”，但我不确定这是否有资格作为证据。

特别是，我们在查看排序函数时遇到了麻烦。例如，std::sort:

Complexity: O(N log(N)) (where N == last - first) comparisons

由于log(0)一般被认为是未定义的，而我不知道0*undefined是什么，会不会是这里有问题？

---

^{(是的，好吧，我有点迂腐。当然，没有 self 尊重的 stdlib 实现会导致空范围传递给 std 的实际问题: :sort。但我想知道这里的标准措辞是否存在潜在漏洞。)}

Answer 1

Big-O 符号是根据函数的极限定义的。 实际 运行时间 g(N) 的算法是 O(f(N)) 当且仅当 lim N→∞ g(N)/f(N) 是一个非负实数 g(N)/f(N) 小于某个正实数C 对于所有大于某个常量 k 的值 N(C 和 k 是无关紧要的；您只需要能够找到任何 C 和 k 就可以了)。 (感谢您的更正，杰西!)

您会注意到元素的实际数量与大 O 分析无关。 Big-O 分析没有说明算法对少量元素的行为；因此，f(N) 是否定义为 N=0 并不重要。更重要的是，实际 运行时行为由不同 函数g(N) 控制，它很可能定义在N= 0 即使 f(0) 未定义。