algorithm - 定长循环的时间复杂度

Question

我很难决定如何陈述类中函数的最坏情况下的运行时复杂度。

这个类存储两种对象，比如 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²)。甚至可以摊销 O(1)？

Answer 1

K is a given constant that doesn't depend on N and M

请注意，句子的第一部分和最后一部分并不自相矛盾。

如果k不依赖于 M,N - 这并不意味着它不会独立生长。如果它确实增长(以什么速度无关紧要)，of 是你的函数的一个参数 - 复杂性取决于它并且确实是 O(k^2) .

如果k是不变的，永远不会改变，这确实是 O(1)，因为 k^2 < C对于一些常量 C=k^2+1 .

在迭代中使用常量值的常见示例是:

• 在执行字符串算法时遍历有限大小的字母表(例如 trie)
• 检查固定整数位。

这些被视为O(1) ，即使它们是用循环实现的，重要的是 - 时间 处理循环受有限大小的限制。