我只是在研究数据结构时编写了一个关于数组旋转的代码。我需要知道如何通过测量时间和空间复杂性来改进下面的程序。
数组旋转程序。将数组旋转为2将使数组
1,2,3,4投入
3,4,1,2产出
public class Program
{
public static void Main(string[] args)
{
int arrayCount = 0;
int rotate = 2;
int []answer = new int[4];
for (int i = 0; i < answer.Length; i++)
{
answer[i] = Convert.ToInt32(Console.ReadLine());
}
arrayCount = answer.Count();
ArrayRotation.displayRotatedArray(answer, rotate, arrayCount);
ArrayRotation.printArray(answer, arrayCount);
Console.ReadKey();
}
}
public static class ArrayRotation
{
public static void displayRotatedArray(int []temp, int rotate, int count)
{
int c = rotate;
int d = rotate;
int[] firstOccurenceArray = new int[rotate];
for (int g = 0; g < rotate; g++)
{
int num = g;
firstOccurenceArray[g] = temp[g];
}
for (int i = 0; i < temp.Length - c; i++)
{
temp[i] = temp[rotate];
rotate++;
}
for (int k = 1; k < d + 1; k++)
{
temp[count - k] = firstOccurenceArray[c - 1];
c--;
}
}
/* utility function to print an array */
public static void printArray(int[] temp, int size)
{
for (int i = 0; i < size; i++)
Console.Write( temp[i] + " ");
}
}
发布于 2018-06-20 12:20:41
计算时间复杂度:操作数随输入参数大小的变化而变化的因素。
在本例中,操作正在发生变化,如前所述:
(2) + 2*旋转+2* temp.Length +2*旋转
对于最大值,它可以是2+ (6 * temp.Length),因此时间复杂度是O(n)。
空间复杂度:O(旋转),可以最大到O(n)
您可以在O(n)时间复杂度和O(1)空间复杂度中通过对数组值的就地交换(杂耍算法)来优化这个问题。
发布于 2018-06-20 10:51:30
时间复杂度: O(n),其中n=数组的长度(因为没有嵌套的for循环)
空间复杂度: O(2),即O(1) (因为这个数组firstOccurenceArray的大小是常数的,即2)
https://stackoverflow.com/questions/50946198
复制相似问题