我很难决定如何声明类中函数的最坏情况的运行时复杂性。
此类存储两种对象，例如N和M，可能有数百万个对象。
其中一项操作只是搜索存储项目的最佳位置：
void foo(item) {
for (int i=0;i<K;i++) {
for (int j=i;j<K;j++) {
if(store(i,j,item)) // store is O(1)
return;
}
}
}
在这里，K是一个问题定义的常数（例如10）。在最坏的情况下，该项目可能不会存储，并且循环将被耗尽。
我不确定foo是否具有O（1）复杂度是否更正确，因为K是一个不依赖于N和M的给定常数；或者最好说复杂度是O（k 2）。甚至还可以摊销O（1）？
K是不依赖于N和M的给定常数
请注意，句子的第一部分和最后部分不是自相矛盾的。
如果k不依赖M,N-这并不意味着它不会独立增长。如果它确实增长（以什么速率无关紧要），则是函数的参数-复杂度取决于它，并且的确是O(k^2)。
如果k为常数且永不改变，则确实为O（1），因为k^2 < C对于某些常数 C=k^2+1。
在迭代中使用常量值的常见示例有：
O(1)即使将它们用循环实现，这些也被视为重要的是-处理循环的时间由有限的大小限制。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句