这个函数的时间复杂度是多少，有人能解释一下吗？
void fun(int n) { int i,j,k, count = 0; for(i = n/2; i <= n; i++) for(j = 1; j <= n; j = 2*j) for(k = 1; k <= n; k++) count++; }
我试图找到给定函数的时间复杂度，我认为第二个循环是O（n），但有人说它是O（log（n））。
gojuced71#
外层循环将执行n/2次迭代。在其每次迭代中，中间循环将执行log(n)次迭代，因为在每一步j都乘以因子2。在其每次迭代中，内层循环将执行n步。所以复杂度是O(n/2 * log(n) * n) = O(n^2 * log(n))。
n/2
log(n)
n
O(n/2 * log(n) * n) = O(n^2 * log(n))
bcs8qyzn2#
时间复杂度O（n/2）O（log（n））的复杂度是O（log（n））。内部循环（k）的复杂度为O（n）如果它们是嵌套的，则函数以n表示的总复杂度为(n/2) * log(n) * n = n² * log(sqrt(n))，考虑到大O符号，其渐近地给出O(n² * log(n))
(n/2) * log(n) * n = n² * log(sqrt(n))
O(n² * log(n))
2条答案
按热度按时间gojuced71#
外层循环将执行
n/2次迭代。在其每次迭代中，中间循环将执行log(n)次迭代，因为在每一步j都乘以因子2。在其每次迭代中，内层循环将执行n步。所以复杂度是
O(n/2 * log(n) * n) = O(n^2 * log(n))。bcs8qyzn2#
时间复杂度O（n/2）
O（log（n））的复杂度是O（log（n））。
内部循环（k）的复杂度为O（n）
如果它们是嵌套的，则函数以n表示的总复杂度为
(n/2) * log(n) * n = n² * log(sqrt(n))，考虑到大O符号，其渐近地给出O(n² * log(n))