Answer the question
In order to leave comments, you need to log in
Should the number of iterations correspond to the asymptotic complexity of the algorithm?
At the moment I'm studying algorithms, and there was some misunderstanding of the term asymptotic complexity of an algorithm.
For example: we know that the SelectionSort algorithm has O(n^2) complexity in both the best and worst case.
I count the number of iterations in my algorithm, and with n=100 we always get the number of iterations 5050. With n=200 - 20100 iterations, n=1000 500500 iterations. The array is filled with random values each time.
And now I'm completely confused, if we have n^2 complexity, should this mean that the number of iterations should be n^2 ?
Or maybe I'm inserting the counter in my code incorrectly?
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 the question
In order to leave comments, you need to log in
Yes, that's right. The actual number of cycle steps is (n ^ 2 + n) / 2. To estimate O, it is enough to indicate the function whose argument is n and which has the largest order of growth, in this case it is quadratic. All multipliers that scale the function itself do not count.
If it would be (2n) ^ 2 - that is another matter.
https://habr.com/post/104219/
PS: If you strictly calculate O, then you need to analyze the expression lim {n -> infinity} (((n^2 + n) / 2) / (n ^ 2)) .
Your iteration counter is incremented 2 times in the code. In the outer loop, there is clearly an extra increment.
In the case of operations on arrays or lists, the complexity estimate is usually taken as the number of complete passes through the array to obtain a result.
In your case, the number of iterations is equal to the complexity score.
In the general case, the number of iterations approaches from the bottom to the complexity estimate, for example, searching the same binary tree can be performed in a different number of steps for different values.
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question