java - 在循环中查找 avg 语句，如 Big O、O(n) 等

Question

离我很近，我能尝到它的味道!我要对我的方法中的所有语句进行计数，并找到某个值“n”的平均语句数。所以我相信就我的语句计数器而言，我已经正确设置了所有内容，但我不确定如何以我可以为每个“n”取平均值的方式来计算这个循环。我相信我必须将我的总陈述除以一些东西，但我不确定这个数字是多少——有人能指出我正确的方向吗？我知道我最终应该得到二次 fxn，O(n^2)...

这是我正在评估的方法...

public static int myMethod(int[] array) {
    int statements = 0;
    for (int next = 1; next < array.length; next++) {
        statements++;
        int val = array[next];
        int index = next;
        while (index > 0 && val < array[index - 1]) {
            statements++;
            array[index] = array[index - 1];
            index--;
        }
        array[index] = val;
    }
    return statements;
}

这是调用方法的测试类...

statements = myClass.myMethod(array); //this is the call we want to measure
                     //I believe the statements variable is working correctly.
        avgStatements = statements/(something here?)

编辑:我可能应该提一下该方法的作用...它接受一个整数，比如 5，然后从随机顺序中按升序排列 1 到 5，例如，如果它是 5，我们可以有 4 1 2 3 5，它会将其组织成一个数组，1 2 3 4 5....谢谢!

Answer 1

我不能确定你要计算什么，但如果我猜对了，n 就是数组的大小 (array.length)，你需要计算平均值每个数组成员的语句数。

因此

 avgStatements = statements/array.length

但是如果你想计算所有的语句，你应该注意到内层循环有两条语句(不算语句++)，而外层循环有三条语句。

因此你应该这样算:

public static int myMethod(int[] array) {
    int statements = 0;
    for (int next = 1; next < array.length; next++) {
        statements+=3;
        int val = array[next];
        int index = next;
        while (index > 0 && val < array[index - 1]) {
            statements+=2;
            array[index] = array[index - 1];
            index--;
        }
        array[index] = val;
    }
    return statements;
}