数组左旋转 { 一个初学者程序员与时间复杂度的斗争 }

huangapple go评论67阅读模式
英文:

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 &lt; a.length-1)
                {
                    a[i] = a[i+1]; 
                    i++; 
                }

                a[a.length-1] = k; 
                d--; 
            }

            return a; 

    }

答案1

得分: 2

一个左旋操作在数组上执行了 n 次赋值,因此它是一个 O(n) 的操作。

你正在执行 d 次这些操作。由于 dn 无关,你可以说时间复杂度的一般形式是 O(n*d)。

如果你得到了关于 dn 的相对大小的任何额外信息,你可以进一步细化:

  • 如果 dn 大得多,n 可以忽略不计,你可以说整个操作的时间复杂度是 O(d)。
  • 如果 dn 小得多,d 可以忽略不计,你可以说整个操作的时间复杂度是 O(n)。
  • 如果 dn 的数量级相同,你可以说整个操作的时间复杂度是 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 than n, n is negligible and you could say the time complexity of the entire operation is O(d).
  • If d is much smaller than n, 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 as n, you could say the time complexity of the entire operation is O(n<sup>2</sup>).

huangapple
  • 本文由 发表于 2020年9月30日 15:32:05
  • 转载请务必保留本文链接:https://go.coder-hub.com/64132873.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定