Должно ли количество итераций соответствовать асимптотической сложности алгоритма?

Question

[Dreaded]

В данный момент изучаю алгоритмы, и возникло некое недопонимание термина асимптотической сложности алгоритма.
Например : мы знаем , что алгоритм SelectionSort имеет сложность O(n^2) и в лучшем и в худшем случае.
Я подсчитываю в своём алгоритме количество итераций, и при n=100 мы всегда получаем количество итераций 5050. При n=200 - 20100 итераций, n=1000 500500 итераций. Массив каждый раз заполняется случайными значениями.

И вот я совсем запутался, если сложность у нас n^2, это должно означать, что количество итераций должно быть n^2 ?
Или может быть я неправильно вставляю счётчик в свой код?

function SelectionSort(&$arr) {
	$iteration = 0;
	for($i=0; $i<count($arr); $i++){
		$min_id=$i;
		for($j=$i+1; $j<count($arr); $j++){
			if ($arr[$j] < $arr[$min_id]) {
				$min_id = $j;
			}
			$iteration++;
		}
		$temp = $arr[$i];
		$arr[$i] = $arr[$min_id];
		$arr[$min_id] = $temp;
		$iteration++;
		
	}
	return $iteration;
}

Answer 1

[alexalexes]

Да, верно. Реально количество шагов циклов (n^2 + n) / 2. Для оценки О достаточно указывать ту функцию, аргументом которой считается n и которая имеет самый большой порядок роста, в данном случае - квадратичная. Все множители, которые масштабируют саму функцию в счет не идут.
Если было бы (2n)^2 - то это другое дело.

При вычислении O можно не учитывать постоянные множители в выражениях.

https://habr.com/post/104219/
PS: Если строго высчитывать O, то вам нужно проанализировать выражение lim {n -> бесконечность} (((n^2 + n) / 2) / (n ^ 2)).

Comments

[Roman]

n -> ∞
lim (((n^2 + n) / 2) / (n ^ 2)) = 1/2

Answer 2

[res2001]

У вас счетчик итераций 2 раза инкрементируется в коде. Во внешнем цикле явно лишний инкремент.
В случае операций с массивами или списками, для оценки сложности обычно берут количество полных проходов по массиву для получения результата.

В вашем случае количество итераций равно оценке сложности.

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