Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
我有一个关于在算法中计算时间复杂度的问题。如果您有四个嵌套的 for 循环,是否可以使用诸如 O(n^4) 之类的符号?
很简单,答案是肯定的。四个嵌套循环可以(取决于循环)为 O(n 4 )。
复杂度高于三次的多项式时间算法并不多,但它们确实存在。例如,众所周知的 AKS 素性检验在其原始公式中是 O(k 12 )(其中 k 是输入数字的长度),尽管它最近已减少到 k 7.5。