这是代码，函数接收一个指针*ptr(指向外面的字符数组)。循环只是计算长度。这个函数的复杂度函数是什么。我计算过。
- 这是正确的复杂度函数计算吗？
- 同时，我应该考虑 3 个操作，*, ptr+c , !=
- Astaric * 是解引用，ptr+c 是计算地址，!= 是条件。
最佳答案
当我们说 O(N) 时，我们真的指的是 O(N)+c，其中 c 是常数。这是因为对于非常小的 n，复杂性的特征可能不会表现出来，因为非本质(噪声)可能占主导地位，因此用 c 表示。但是随着 N 的增长，常数变得无关紧要，因为相对于 N 的复杂性成为主导时间。通常，常量只是将图形向上或向下移动少量，但不会改变其形状。因此，我们省略它，只说 O(N)，这是我们真正想知道的。
至于系数，同样的事情发生了。如果复杂度与 N 成正比，则它是线性关系。乘以 X 的线性运算图将具有不同的斜率，但其形状仍然是线性的。因此，该系数并没有真正提供复杂类别方面的额外信息。
类似地，如果你有一个 O(N)+O(N^2) 的东西，N^2 占主导地位，我们倾向于忽略更小的项 O(N)，而只称它为 O(N^ 2)算法。这不是一门精确的科学，而是一种理解复杂性本质的分类。大 O 表示法是最坏情况的复杂性。
我认为您可能只在评估具有相同分类复杂度的特定算法的相关指标时才对系数和常量感兴趣。 (例如，某些 O(N*lg(n)) 排序比其他排序快。)但通常以不同的方式衡量。
关于c++ - 这个指针函数的复杂度是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48813017/