大O：如何确定基于外部for循环的for循环增量的运行时间？ [英] Big O: How to determine runtime for a for loop incrementation based on outer for loop?

问题描述

我有以下算法，运行时复杂度为O（N ^ 2），但我想对其有更深的了解，而不仅仅是记住普通的运行时。

I have the following algorithm and the runtime complexity is O(N^2) but I want to have a deeper understanding of it rather than just memorizing common runtimes.

将其分解并在内部for循环中使用 i + 1 进行分析的正确方法是什么

What would be the right approach to break it down and analyze it with i+1 in the inner for loop taken into account?

void printunorderedPairs(int[] array) {
    for(int i=0; i<array.length; i++) {
        for(int j=i+1; j<array.length; j++) {
            System.out.println(array[i] + "," + array[j]);
        }
    }
}

编辑

询问如何分析特定问题

推荐答案

将其分解和分析的正确方法是什么

What would be the right approach to break it down and analyze it

拿铅笔和纸放下未循环的一些循环：

Take pencil and paper and put down some loops unwraped:

     i        inner loops per i
-------------------------------
     1               length - 1  
     2               length - 2
    ..                       ..  
     k               length - k 
    ..                       ..
length - 1                    1
length                        0

现在，为了获得所需的总时间，让我们总结一下内部循环：

Now, in order to obtain the total time required, let's sum up the inner loops:

 (length - 1) + (length - 2) + ... + (length - k) ... + 1 + 0

算术进步，其总和为

 ((length - 1) + 0) / 2 * length == length**2 / 2 - length / 2 = O(length**2)

这篇关于大O：如何确定基于外部for循环的for循环增量的运行时间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！