Временная сложность алгоритмов в Java

Question

Привет! Я использую следующий универсальный алгоритм пузырьковой сортировки и хочу показать сложность времени. Я понимаю, что лучший / худший случай для этого алгоритма исправлен, но мне было интересно, может ли он быть конкретным для моего массива?

Например, наихудший случай для этого вида - O(n^2), это может быть специфично для моего массива?

Например, наихудшим случаем может быть сортировка 100 из 120 элементов (что я имею в виду под конкретным для моего массива).

public static <E extends Comparable<? super E>> void bubbleSort(E[] comparable) {
    boolean changed = false;
    do {
        changed = false;
        for (int a = 0; a < comparable.length - 1; a++) {
            if (comparable[a].compareTo(comparable[a + 1]) > 0) {
                E tmp = comparable[a];
                comparable[a] = comparable[a + 1];
                comparable[a + 1] = tmp;
                changed = true;
            }
        }
    } while (changed);
}

Answer 1

Сложность - это асимптотическое свойство функции (или алгоритма), а не фактического пути выполнения. Сложность выражает соотношение между размером ввода и временем вычисления (или требованием к пространству). Как таковая, эта концепция не имеет смысла применительно к одному конкретному вычислению.

Другими словами, вы можете спросить о сложности вычислений f(n) в зависимости от n, но не от вычислений f(5). Последний просто номер. Первый является функцией.

То, что вы можете сделать вместо этого, - это подсчитать фактическое количество операций. Каждый раз, когда вы выполняете операцию, которую хотите включить (например, «сравнение»), просто увеличивайте некоторый глобальный счетчик и проверяйте его значение впоследствии. (Сложность алгоритма должна указывать границы для значений, которые может принимать этот счетчик.)

Answer 2

Производительность алгоритма в «наихудшем случае» относится к набору входных данных, который заставляет алгоритм вести себя хуже всего. Поэтому нет смысла ссылаться на «наихудший случай» конкретного входного массива, потому что это всего лишь один случай.

Answer 3

В общем случае сложность вашего алгоритма в худшем случае равна O(n^2) (то есть не более , чем n^2, асимптотически).Это также Theta(n^2) (то есть не больше и не меньше , чем n^2).Я опускаю мультипликативную константу.

Допустим, вы что-то знаете о своем массиве.Если говорить конкретно, скажем, вы знаете, что для сортировки вашего массива требуется не более пяти свопов типа пузырьковой сортировки.С этим знанием все еще правильно сказать, что время выполнения вашего алгоритма O(n^2).Однако уже не Theta(n^2).

также правильно сказать, что время выполнения алгоритма в этом конкретном случае равно O(n).Другими словами, знание чего-либо о массиве позволило нам обеспечить более узкую границу для времени выполнения вашего алгоритма.

Answer 4

Наилучший случай для пузырьковой сортировки возникает, когда список уже отсортирован или почти отсортирован O(n), так что да, это может зависеть от вашего массива.