Оценка сложности алгоритма сортировки

Question

Может ли кто-нибудь помочь мне найти большую букву O для этого метода сортировки, это O (n), O (n log n) или O (n ^ 2)?

for (int i = 1; i < peopleList.size(); i++) {
        for (int j = i; j > 0; j--) {
            Person lower = peopleList.get(j - 1);
            Person higher = peopleList.get(j);

            if (higher.name.compareTo(lower.name) < 0) {
                peopleList.set(j, lower);
                peopleList.set(j - 1, higher);
            } else
                break;
        }
    }

Answer 1

При оценке Big O алгоритма, начните с самого внутреннего блока, оцените его сложность и выйдите.

for (int i = 1; i < peopleList.size(); i++) {  // Will always iterate through the entire list (O(n))
        for (int j = i; j > 0; j--) {  // Best case, this iterates once per outter loop (constant), worst case iterates n times (O(n))
            Person lower = peopleList.get(j - 1);  //constant operation (assuming ArrayList)
            Person higher = peopleList.get(j);  //constant operation (assuming ArrayList)

            if (higher.name.compareTo(lower.name) < 0) {  //constant operation
                peopleList.set(j, lower);  //constant operation
                peopleList.set(j - 1, higher);  //constant operation
            } else {
                break;
            }
        }
    }
}

Затем вы умножите сложность всех слоев циклов.И вы получите лучший случай O (n) и худший случай O (n ^ 2)

Answer 2

Say n = peopleList.size().В приведенном выше коде для каждого элемента в списке peopleList в позиции - i мы выполняем итерации по элементам i, используя другой цикл и проводя вычисления с постоянными значениями.Итак, в целом мы выполняем почти 1 + 2+ 3 + ... + n = n * (n + 1) /2 операций.Следовательно, временная сложность вышеуказанной программы составляет O(n^2).