I have written code to reverse an array that has Time Complexity: O(n).
Is there a faster method?
My code:
void reverseArray(int arr[], int start, int end){
int temp;
if(start >= end)
return;
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
reverseArray(arr, start+1, end-1);
}
Literally reversing the elements in memory can't be done any faster than O(n). However, you could make a wrapper class that indexes the array reversed. So, in fact you don't reverse the array, but only access the elements backwards.
The code you have is O(n), but terrible because of the recursion. Make it flat and you will experience some benefit.
public static void reverseArray(int arr[], int start, int end)
{
int len = end - start;
if(len <= 0) return;
int len2 = len >> 1;
int temp;
for (int i = 0; i < len2; ++i)
{
temp = arr[start + i];
arr[start + i] = arr[end - i - 1];
arr[end - i - 1] = temp;
}
}
You are using recursion which is not as fast as a loop. You are still O(n) but with faster time to use a loop. Something like:
static void reverseArray(int arr[]){
for (int start=0,end=arr.length-1;start<=end;start++,end--) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
}
For something like this you will be better off using methods provided in the Java libraries to do it though.
You could use some intermediary function:
int rev(int i) {
return arr.length - i - 1;
}
//...
arr[rev(i)] = 5; // reverse reference
If you use static arrays, since you will need to access every element once in order to reverse it, there is no smaller complexity than n.
However, if you use a double linked list, then by definiton you have access to the elements in both directions. From head to tail and from tail to head, because there are double pointers in the Node class used. Therefore, reverse is not even needed, but rather you iterate from tail to head when needed.
Recursion vs Iteration. Function calls (recursion) cost cycles. Thus, for this solution, I would go with an iterative approach. Other things to note are: even/odd sized arrays, empty arrays, arrays with only 1 item. An untested solution is:
void reverseArray(int arr[]){
//check input
if(arr.length <= 1){
return;
}
int arrLength = arr.length;
int swpIndex;
for (int i = 0; i < arrLength / 2 - 1; i++){
swpIndex = arrLength - i - 1;
swp = arr[i];
arr[i] = arr[swpIndex];
arr[swpIndex] = swp;
}
}
This stores a few values so that it really avoids repitition (i.e. extra cycles). It also checks for arrays that don't need reversing.
ArrayUtils.reverse(int[] arr)from apache library.