嵌套循环的运行时间 [英] Run time of nested loops

问题描述

对不起，如果已经问过这个问题，我不确定如何搜索.

Sorry if this question has already been asked, I wasn't sure how to search for it.

假设您有以下循环

    for (i=0; i < n; i++)
         for(j = i; j < n; j++)

这是O(n ^ 2)还是O(nlog(n))，为什么?

Would this be O(n^2) or O(nlog(n)) and why?

推荐答案

外循环的运行时间(本身)为O(n)，内循环的运行时间为O(n-i).因此，循环的时间为(n)(n-i)，当您丢弃常数i时，运行时间将为O(n ^ 2).

The outer loop's runtime (by itself) is O(n), and the inner loop's runtime is O(n-i). So the loop's time would be (n)(n-i), and when you throw away the constant i, the runtime would be O(n^2).

这篇关于嵌套循环的运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！