0

我有一个关于在算法中计算时间复杂度的问题。如果您有四个嵌套的 for 循环,是否可以使用诸如 O(n^4) 之类的符号?

4

1 回答 1

2

很简单,答案是肯定的。四个嵌套循环可以(取决于循环)为 O(n 4 )。

复杂度高于三次的多项式时间算法并不多,但它们确实存在。例如,众所周知的 AKS 素性检验在其原始公式中是 O(k 12 )(其中 k 是输入数字的长度),尽管它最近已减少到 k 7.5

于 2013-02-07T22:46:57.333 回答