麻烦请问一下大家,这个程序的算法复杂度是多少呢,我算的是o(n的四次方),但是并不对.
首先,这里只有3重循环,最多也只有3次方,4次方是怎么算出来的?
再看每重循环,除了最外层从1到n,内层都是从1到i,或者从1到j
那么如果你懂几何的话,这其实围成一个三维图形
底面是个三角形,上面是个三棱锥
最终其实就是求三棱锥的体积,应该是n立方除以3
这是一个三重循环,就是o(n的三次方)。
一个函数调用或是一组语句都认为是O(1)的复杂度 (如果没有调用不包含循环,递归或其他非常量复杂度的函数)。
如果在一个大小为n循环中,循环变量按照一个常量C递增或递减,这个循环的复杂度就为O(n)。
嵌套循环的时间复杂度等于行最内层语句执行的次数。
O(N^3)