英文:
Arrays Left Rotation { A baby coder's struggle with time complexities}
问题
我正在解决一个Hackerrank的问题,我被给定了一个数组,必须将元素向左旋转n次。我已经解决了这个问题,但我仍然困在如何计算解决方案的时间复杂度上,因为我要穿越数组n次,并且在while循环条件为false之前将i初始化为0,我想说时间复杂度是O(n),但我更倾向于是O(n^2),或者我完全错了...有人能帮我理解计算时间复杂度的方法吗?我知道我的空间复杂度是O(1),因为我没有使用额外的数据结构。最后,根据实际的时间复杂度,是否有必要使我的代码更加高效? 顺便说一下,请友善地回复,我是一名本科生,仍在努力掌握基本的计算机科学原理。如果您有任何关于学习时间复杂性的好书或网站建议,如果您能在评论中提供链接,我将不胜感激。
这是问题的描述:
对数组执行左旋转操作,将数组中的每个元素向左移动d个单位。例如,如果在数组[1,2,3,4,5]上执行2次左旋转,则数组将变为[3,4,5,1,2]。
给定一个整数数组n和一个数字d,在数组上执行d次左旋转。返回更新后的数组,以单行用空格分隔的整数形式打印出来。
这是我的输入:
5 4
1 2 3 4 5
n = 5 d = 4
这是我的输出:
5, 1, 2, 3, 4
我的解决方案/代码:
static int[] rotLeft(int[] a, int d) {
while (d != 0) {
int k = a[0];
int i = 0;
while (i < a.length - 1) {
a[i] = a[i + 1];
i++;
}
a[a.length - 1] = k;
d--;
}
return a;
}
英文:
I am working on a Hackerrank problem where I am given an array and must rotate elements to the left n amount of times. I was able to solve the problem but I am still stuck on how to calculate the time complexity of my solution since I am traversing through the array n amount of times and initializing i at 0 until the while loop condition is false, I wanted to say O(n), but I'm leaning towards O(n^2) or I'm just way off... Can someone please help me understand the approach to calculating time complexities? I know that my space complexity is O(1) since I am not using an extra data structure. Lastly, depending on the actual time complexity is there a need to make my code more efficient? P.S. please be kind with your responses, I am an undergrad still trying to master basic Computer Science principles. If you have any good books or website suggestions specifically for learning time complexities I'd be so grateful if you'd provide a link in the comments.
Here is the question:
A left rotation operation on an array shifts each of the array's elements unit to the left. For example, if 2 left rotations are performed on the array [1,2,3,4,5], then the array would become [3,4,5,1,2].
Given an array of integers n and a number, d, perform d left rotations on the array. Return the updated array to be printed as a single line of space-separated integers.
Here is my input:
5 4
1 2 3 4 5
n = 5 d = 4
Here is my output:
5, 1, 2, 3, 4
My Solution/Code :
static int[] rotLeft(int[] a, int d) {
while(d != 0)
{
int k = a[0]; int i = 0;
while(i < a.length-1)
{
a[i] = a[i+1];
i++;
}
a[a.length-1] = k;
d--;
}
return a;
}
答案1
得分: 2
一个左旋操作在数组上执行了 n
次赋值,因此它是一个 O(n) 的操作。
你正在执行 d
次这些操作。由于 d
与 n
无关,你可以说时间复杂度的一般形式是 O(n*d)。
如果你得到了关于 d
和 n
的相对大小的任何额外信息,你可以进一步细化:
- 如果
d
比n
大得多,n
可以忽略不计,你可以说整个操作的时间复杂度是 O(d)。 - 如果
d
比n
小得多,d
可以忽略不计,你可以说整个操作的时间复杂度是 O(n)。 - 如果
d
与n
的数量级相同,你可以说整个操作的时间复杂度是 O(n^2)。
英文:
A left rotation performs n
assignments on the array, so it's an O(n) operation.
You're performing d
of those operations. Since d
is unrelated to n
, you could say that the general form of the time complexity is O(n*d).
If you were given any additional information about the relative sizes of d
and n
, you could further refine this:
- If
d
is much larger thann
,n
is negligible and you could say the time complexity of the entire operation is O(d). - If
d
is much smaller thann
,d
is negligible and you could say the time complexity of the entire operation is O(n). - If
d
is the same order of magnitude asn
, you could say the time complexity of the entire operation is O(n<sup>2</sup>).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论