我想知道,如果for循环在N和某个指定整数上循环,那么如何找到算法的大OH复杂性。例如,一个函数的复杂性是什么?

for (int i=0; i < n; i++) {
    for (int j=0; j < 100; j++) {
        for (int k=0; k < n; k++) {
            // Some O(1) operation here.
        }
    }
}

现在,我知道外环和最内层for循环都具有复杂性O(n),但是中间环的复杂性是什么呢?O(100),会减到O(1)吗?

最佳答案

是的,只有中间的那个才是O(1)这意味着不管我的输入是什么,它都会运行100次你不能再让它循环了。
但它们最外层和最内层都依赖于n。如果n是100,那么ouermost运行100次如果它是1000000,那么它运行1000000次。
最内部的回路呢对于最外层的每次迭代,它运行100*n次。总的来说,它会运行100*n*n次。
现在想想他们总共做了多少工作?
n
100n^2+100n+n = An^2+B将是时间复杂度。
o(10)或o(100)与o(100000)是否相同?
好吧,我会帮你省去写更多的东西,因为任何常数都等于。
这里c是10,100,100000。

关于algorithm - 在n和一个精确整数上嵌套的for循环的复杂性?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/47001358/

10-09 08:25
查看更多