What is the time complexity of this algorithm
https://softwareengineering.stackexchange.com/questions/420571
-
20-03-2021 - |
質問
This code is from https://www.geeksforgeeks.org/segregate-even-and-odd-numbers/
It takes an array of numbers & segregates them in place without bothering about the order.
void segregateEvenOdd(int arr[], int size)
{
/* Initialize left and right indexes */
int left = 0, right = size-1;
while (left < right)
{
/* Increment left index while we see 0 at left */
while (arr[left] % 2 == 0 && left < right)
left++;
/* Decrement right index while we see 1 at right */
while (arr[right] % 2 == 1 && left < right)
right--;
if (left < right)
{
/* Swap arr[left] and arr[right]*/
swap(&arr[left], &arr[right]);
left++;
right--;
}
}
}
The site mentions that this algorithm is O(n).
However, since there is an inner loop and an other loop, I don't think this is O(n). Since the inner loop doesn't run through for each iteration of the other loop, it's not O(n^2) either.How does one analyse the complexity of this algorithm? I think it's an O(nlogn) algorithm but I am not sure how to arrive at that?
解決
It's basically just one loop that scans from left
and right
to a midpoint.
Here's a simpler version that does the same thing (though omits optimizations):
void segregateEvenOdd(int arr[], int size)
{
int left = 0;
int right = size - 1;
while (left < right)
{
if (arr[left] % 2 == 0)
{
left++;
}
else if (arr[right] % 2 == 1)
{
right--;
}
else
{
swap(&arr[left], &arr[right]);
}
}
}
Or in tabular form:
void segregateEvenOdd(int arr[], int size)
{
int left = 0;
int right = size - 1;
while (left < right)
{
if (arr[left] % 2 == 0) { left++; }
else if (arr[right] % 2 == 1) { right--; }
else { swap(&arr[left], &arr[right]); }
}
}
So the claim that it's O(n) makes sense, where n is the size of the loop and presumably other operations are assumed to be O(1).