@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]));
  • Вопрос задан
  • 3139 просмотров
Пригласить эксперта
Ответы на вопрос 2
@dmshar
Открою вам маленький секрет, который вам должны были рассказать на первой же лекции по теории алгоритмов. Если вы возьмете тот-же массив, перетасуете его и еще раз отсортируете, то велика вероятность того, что получите ответ, отличный от 28.
И вам наверняка говорили, что O(n) - это вовсе не время и даже не количество операций, которые надо выполнить. На самом деле О - нотация показывает как изменяется количество выполнимых операций при соответствующем увеличении входных данных.
Соответственно O(n) говорит, что с ростом объема количество операций растет (примерно) линейно, а O(n^2) - растет (примерно) квадратично.
Если хотите удостовериться - надо проводить такой эксперимент. Берете набор данных на Х элементов, 100000 раз его тасуете и 100000 проводите сортировку. Получаете некоторую усредненное число повторений A. Потом берете набор данных на 2Х элементов и повторяете процедуру. Получаете усредненное количество операций В. И смотрите, в каком отношении находятся В и А. Вот это и есть грубая оценка О(.).
Ответ написан
origami1024
@origami1024
went out for a night walk
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)
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы