为什么我的时间计算与复杂度的演化曲线不一样？

Question

假设我有一定数量的学校和一定数量的学生。 对于每个学生，我想使用随机系数根据他们的旧成绩计算新成绩。 我使用的数组与学校的数量一样多，并且它们都是每所学校的学生人数。

所有学校的学生总数始终恒定。 我想要改变的是学校的数量。 因此，如果我们有更多的学校，每所学校的学生就会减少。 由于我们始终拥有相同数量的学生以及每个学生的计算量，因此即使更改学校数量，我们也将始终具有相同的计算量。

那么当学校数量不同时，总的计算时间应该是相同的吧？

嗯，显然是错误的。当我进行计算时（我每次都在多次迭代中使用平均值，以便进行更有意义的时间计算），时间计算的数量根本不是恒定的，并且随着学校数量的增加而增加。

有人解释一下吗？

public static Long changeNotesComputationTime(Random random, int nIterations, int nSchools, int nStudents) {
    long[] timePerIteration = new long[nIterations];
    int nStudentsPerSchool = nStudents / nSchools;
    for (int iIteration = 0; iIteration < nIterations; iIteration++) {
        System.out.println(iIteration + " iteration");
        long computationTime = 0;
        for (int iSchool = 0; iSchool < nSchools; iSchool++) {
            int[] gradesOfStudents = random.ints(nStudentsPerSchool, 0, 20).toArray();
            double coeff = random.nextDouble();
            int[] gradesChangedOfStudents = new int[nStudentsPerSchool];
            long startComputations = System.currentTimeMillis();
            for (int iStudent = 0; iStudent < nStudentsPerSchool; iStudent++) {
                gradesChangedOfStudents[iStudent] = (int) (gradesOfStudents[iStudent] * coeff);
            }
            long endComputations = System.currentTimeMillis();
            computationTime += endComputations - startComputations;
        }

        timePerIteration[iIteration] = computationTime;
    }
    return Arrays.stream(timePerIteration).sum() / nIterations;
}

    @Test
    public void Test() throws PerformanceException, IOException {
        final Writer writer = Files.newBufferedWriter(Paths
                .get(outputPathFolder, "ComputationTime.csv"), Charset.defaultCharset());

        final int nIterations = 100;
        final int nStudents = 10000000;

        writer.write(
                "number of schools; computation time [ms]\n");
        for (int nSchools = 5000000; nSchools < nStudents; nSchools += 500000) {
            writer.write(Long.toString(nSchools) + ";");
            writer.write(
                    Long.toString(Fixture.changeNotesComputationTime(random, nIterations, nSchools, nStudents))
                            + "\n");
        }
        writer.close();
    }

这是我获得的曲线：

编辑：我知道我们可以争论学生人数每次可能不完全相等，因为学生人数可能无法被学校数量整除，但在我使用的真实代码中，我确保情况确实如此，并且我还是有上升曲线

Answer 1

错误非常微妙，它与您选择的值有关，在第一次迭代中您有：

nSchools = 5000000;
nStudentsPerSchool = 2;

第二个：

nSchools = 5500000;
nStudentsPerSchool = 1;

而接下来的时间里，学校的数量会继续增加，但学生的数量仍然是“1”，这就是错误的根源。

nSchools = 6000000;
nStudentsPerSchool = 1;

nSchools = 6500000;
nStudentsPerSchool = 1;

....