Таким образом, цикл while
равен O (n) при первоначальном вызове.Если мы примем массив [1, 2, 3, 4, 5]
, то первый раз в цикле list[equal] == pivot
, и мы увеличиваем equal
.
Второй и последующие моменты в цикле, list[equal] > pivot
, поэтому мы уменьшаемlarger
и поменяйте местами с этим элементом.Когда цикл закончен, у вас есть equal=1
, а smaller
не изменился.Ваши рекурсивные вызовы становятся:
dutchSort(list, 0, 0)
dutchSort(list, 1, n)
Итак, один из предметов выпал.
Сделайте то же умственное упражнение a для еще нескольких глубин рекурсии, и я думаю, вы получитеИдея о том, как работает разбиение.
Чтобы ваш алгоритм был O (N ^ N), он должен был бы сравнить каждый элемент с каждым другим элементом несколько раз.Но этого не происходит, потому что на каждом уровне рекурсии вы разбиваете проблему на две части.Как только что-то разбито на левую половину массива, его невозможно сравнить с чем-то, что было перемещено в правую половину массива.Таким образом, в худшем случае каждый элемент сравнивается с любым другим элементом.Это будет O (N ^ 2).
Когда все элементы равны, алгоритм равен O (N).
Я думаю, что сложность алгоритма определяется количеством уникальных предметов.Не похоже, что начальный порядок массива будет иметь какое-либо влияние.