Выбор сортировки Big-Oh

Question

Какие шаги необходимы для определения нотации Биг-О для алгоритма при сортировке массива целых чисел 5 7 4 9 8 5 6 3 и отображении содержимого каждый раз, когда сортировка выбора изменяет его, сортируя массив в порядке возрастания ив порядке убывания?Мне нужно оценить нотацию Big-Oh, прежде чем я придумаю Java-программу для сортировки элементов в порядке возрастания и убывания

Answer 1

При нахождении Big Oh для любого алгоритма вы должны посчитать количество инструкций, которые выполняются в алгоритме, обычно путем нахождения схемы, когда они выполняются.Вы также должны учитывать инструкции, которые встречаются в худшем случае (т. Е. При поиске в списке худшим случаем является посещение каждого элемента).Для сортировки выбора упрощенная разбивка алгоритма состоит в том, что для списка из n элементов каждый элемент сравнивается с другими элементами в списке.Переключение элементов и печать n элементов также происходит по существу для каждого элемента.Примерно это будет выглядеть так в коде:

• Для каждого n элемента

  -Пройдите по списку и сравните с каждым другим элементом справа от элемента

  -Если минимальный элемент в правой подмассиве меньше текущего элемента, переключите

  -Печать n элементов в массиве.

Так будет выглядетьn * (n + 1 + n), что по существу равно O (n ^ 2). Если ваш алгоритм хочет сделать как восходящий, так и нисходящий, он удваивает n ^ 2, который по-прежнему равен O (n ^ 2)