时间戳

首页 > 解决方案 > Arrays Left Rotation { 小程序员与时间复杂性的斗争}

java - Arrays Left Rotation { 小程序员与时间复杂性的斗争}

问题描述

我正在研究一个 Hackerrank 问题，我得到一个数组，并且必须将元素向左旋转 n 次。我能够解决这个问题，但我仍然坚持如何计算我的解决方案的时间复杂度，因为我正在遍历数组 n 次并将 i 初始化为 0 直到 while 循环条件为假，我想说O（n），但我倾向于O（n ^ 2）或者我刚刚离开......有人可以帮我理解计算时间复杂度的方法吗？我知道我的空间复杂度是 O(1)，因为我没有使用额外的数据结构。最后，根据实际的时间复杂度，是否需要让我的代码更高效？PS请善待您的回答，我是一名仍在努力掌握基本计算机科学原理的本科生。

这是问题：

数组的左旋转操作将数组的每个元素单元向左移动。例如，如果对数组 [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; 

    }

标签： javaarrays

解决方案

左旋转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 )。

推荐阅读