Как подсчитать количество операций при работе алгоритма сортировки?

Question

[randomguyasking]

Ниже представлен код, в котором реализован обычный алгоритм сортировки выбором. Напомню, что сложноть этого алгоритма O(n^2). Я передаю в функцию сортировки массив размером 7 элементов. Если посчитать O(n^2), то получается 7 * 7 = 49 операций. В коде я пытаюсь посчитать тоже самое, создав переменную operations и инкрементируя её в конце каждой итерации цикла, ведь, итерация - это и есть операция (или нет?). В итоге у меня получилось 28, хотя ожидал увидеть 49. Где моя ошибка?

const sort = (collection) => {

let operations = 0;
const length = collection.length - 1;
	
  for (let i = 0; i <= length; i++) {
		let minIndex = i;
    for (let j = i + 1; j <= length; j++) {
      if (collection[j] < collection[minIndex]) {
        minIndex = j;
			}
			operations++;
		}
		if (minIndex !== i) {
			[collection[minIndex], collection[i]] = [collection[i], collection[minIndex]];
		}
		operations++
	}
	console.log('Количество операций: ', + operations);
	return collection;
};
console.log(sort([2, 1, 3, 5, 6, 3, 9]));

Answer 1

[dmshar]

Открою вам маленький секрет, который вам должны были рассказать на первой же лекции по теории алгоритмов. Если вы возьмете тот-же массив, перетасуете его и еще раз отсортируете, то велика вероятность того, что получите ответ, отличный от 28.
И вам наверняка говорили, что O(n) - это вовсе не время и даже не количество операций, которые надо выполнить. На самом деле О - нотация показывает как изменяется количество выполнимых операций при соответствующем увеличении входных данных.
Соответственно O(n) говорит, что с ростом объема количество операций растет (примерно) линейно, а O(n^2) - растет (примерно) квадратично.
Если хотите удостовериться - надо проводить такой эксперимент. Берете набор данных на Х элементов, 100000 раз его тасуете и 100000 проводите сортировку. Получаете некоторую усредненное число повторений A. Потом берете набор данных на 2Х элементов и повторяете процедуру. Получаете усредненное количество операций В. И смотрите, в каком отношении находятся В и А. Вот это и есть грубая оценка О(.).

Comments

[ayazer]

^ this. так-же добавлю что О - это аппроксимация. В случае с алгоритмом сортировки через вставку - сложность можно записать как (чесно стырино с вики, набирать ручками было лениво). Если откроете скобки получите что сложность = 1/2 * n^2 - 1/2 n. а O(1/2 * n^2 - 1/2 n) = О(n^2) т.к. откидываем константы

[randomguyasking]

Ясно. Ну я только начал все изучать. Полагал, что раз для O(log n) можно посчитать кол-во операций, то и все другое можно посчитать. Например, при 10 элеметах операций будет 3, при 100 будет 7 и так далее. А выходит, для O(n ^ 2) так не получится.

[origami1024]

Если вы возьмете тот-же массив, перетасуете его и еще раз отсортируете, то велика вероятность того, что получите ответ, отличный от 28.

randomguyasking, да этот чел хрень впаривает, он даже твой код не посмотрел, что у тебя алгоритм, который всё время макс кол-во итераций делает вне зависимости от входных данных

[dmshar]

origami1024, Мил человек. Не стоит быть столь резким в суждениях. Человек написал алгоритм, причем написал его не оптимально. Ну привел-бы ты правильную реализацию. Чеж-нет? А если бы привел, то увидел, что то, что я сказал - верно. Не по цифрам, а по сути вопроса - "как измерить сложность алгоритма".
Ясно, при не оптимальном алгоритме у ТС будут завышенные цифры.
Но еще раз - при определении сложности конкретные цифры не значат ничего.
Значение имеет только отношение изменения цифр к изменению объема данных.
Что-.бы не быть голословным - берем "правильную" реализацию алгоритма сортировки выбором например отсюда: https://medium.com/@alivander/сортировка-выбором-j...
и понимаем, что то, что я написал - это не "впаривание хрени", а наоборот, объяснение принципов. А "орфографические ошибки" в программах исправлять - так это я оставлю внимательным молодым кодерам.

[origami1024]

dmshar,
По этой ссылке, что ты приводишь точ в точ алгоритм ОПа, дело не в "орфографических" ошибках. И там так же как у ОПа - сильно грубо для подсчета на практике оценена сложность алгоритма O(N^2)

Когда дело доходит до подсчета операций, как раз лучше забыть про всякие лекции и рассчитать более точную сложность алгоритма, которая не O(N^2) а O(N^2) минус значимое кол-во.
Ты ОПу втираешь, то что у него 28 операций ему следует просто игнорировать и считать, что по сути там 49. Но у тебя полностью ошибочная причина для этого, при перетасовке данных кол-во операций у него всё время будет 28

[randomguyasking]

берем "правильную" реализацию алгоритма сортировки выбором например отсюда

абсолютно такая же реализация, как и у меня. В чем её правильность?

По этой ссылке, что ты приводишь точ в точ алгоритм ОПа

да, двум людям не может казаться.

[dmshar]

более точную сложность алгоритма, которая не O(N^2) а O(N^2) минус значимое кол-во.
Вот там, наверху, в одном из дополнений к ответу показано, чему это "значимое" равно. Например, при N=10000. (Всего!!! я про миллионные наборы даже не говорю). Так вот при этом получаем N^2=100000000 = 10^8. Можно ли считать уменьшение на 10000, т.е. на 0.001% (ноль целых, одну тысячную процента ) значимым?
Так что своя теория - это хорошо. Но вот "всякие лекции" говорят, что если
N возрастет в 2 раз, до N=20000 то количество операций станет 4*10^8, "значимое" уменьшение станет равным 20000, т.е. вообще 0.0005%.
Имеет-ли это "уменьшение" хоть какое-то реальное значение?

Именно про это я и сказал - Значение имеет только отношение изменения цифр к изменению объема данных. Которое в данном алгоритме равно квадрату от объема. Ага, с микроскопическим уменшением.

[dmshar]

randomguyasking, Да, каюсь, забыл, что у сортировки выбором - в отличии от других методов сортировки - сложность не меняется для лучшего, среднего и худшего случая. Можете для этого случая фразу про пересортировку массива выкинуть (хотя - все таки оставьте, для других методов - пригодится, там ситуации разного количества циклов для перетасованных данных будут встречаться постоянно и с ними придется разбираться). Остальное там написанное не "хрень", а объяснение того, что такое сложность,что она на самом деле означает и как ее определять - а в комментариях, еще и что такое "значимое кол-во".

[raihzel96]

origami1024, как посчитать с помощью формулы количество операций? У меня есть ориентированный граф. Я нашла кратчайший путь с помощью 3-х методов : Dijkstra,Bellman-Ford-Moore, Pape. Теперь я сравниваю алгоритмы с точки зрения количества итераций и операций. Как посчитать сколько операций в 1 итерации?

Answer 2

[origami1024]

for (let i = 0; i <= length; i++) {
    let minIndex = i;
    for (let j = i + 1; j <= length; j++) {

У тебя тут не O(N^2) сложность.
Внутренний массив считает не с начала до конца, а от текущего элемента внешнего массива.
У тебя что-то между O(NlogN) и O(N^2)

Comments

[Wataru]

Ах, если бы для достижения логарифма достаточно было гнать внутренний цикл с индекса внешнего...

Если аккуратно подсчитать количество итераций, то будет N(N-1)/2 (потому что N+(N-1)+(N-2)+...+2+1).

Это в точности N^2/2 - N/2, что есть O(N^2). Более того, оно будет $Theta$(N^2). Т.е. не будет O() для чего угодно быстрее N^2.

O(N log N) тут даже близко не пахнет.