Блог

Мне дали этот алгоритм, который берет максимальный элемент (назовем его m) в массиве A и разбивает вокруг него таким образом, что все элементы, меньшие m, попадают в набор A1, а все те, что больше или равны, попадают в A2. В конечном счете, он выполняется рекурсивно на A1 и использует InsertionSort на A2. Он завершается после объединения A1 и A2 в A.

Прежде всего, я действительно не понимаю, почему он использует InsertionSort для A2 (я имею в виду, m — это максимум, поэтому A2 будет содержать только элементы, равные максимуму). В любом случае, один из вопросов касается поиска наихудших и наилучших сценариев и их временной сложности. Что касается наихудшей временной сложности, я думаю, что это O (n ^ 2), но я не совсем уверен (это должно быть похоже на selectionSort, верно?) Что касается остального, я действительно не знаю..