优化运行时（嵌套循环和数组的浅拷贝）

Question

以下代码的运行时间太长了long.I我想知道我是否要优化代码，我应该为嵌套循环寻找替代方案还是数组的浅拷贝是原因。我知道嵌套循环的时间复杂度是 O(n^2) 而浅拷贝的时间复杂度是 O(n)。这是否意味着运行时间长的原因是嵌套循环？

import copy

def rotLeft(a, d):
    
    size_a = len(a)
    
    temp_array = [0]* size_a
    
    for i in range (d):
        # Moving all elements to a new temp_array with updated indecies
        
        for j in range (size_a - 1):#0,1,2,3
            
            temp_array[j] = a[j+1]
            
        temp_array[size_a - 1] = a[0]#it is recognizing the a as the same as temp_array
        
        a = copy.copy (temp_array)#Shallow copy
        
#         print(a)
        
    for i in range (len(a)):
        
        print(a[i] , end = ' ')

a = [1, 2, 3, 4, 5]

d = 4

rotLeft(a, d)

Answer 1

您已通过旋转数组 d 次来实现 rotLeft。这意味着你的算法的运行时间是 O(d * n)。您可以通过从头开始将数组旋转 d 来避免这种情况。

def rotLeft(a, d):
    d = d % len(a)
    return a[d:] + a[:d]

a[d:] 从索引 d 开始获取输入列表的一部分，并且 a[:d] 从第一个索引到索引 d 获取列表，从而实现了你想要的旋转。连接列表是一个 O(n) 操作。

编辑： 取列表长度的 mod 来处理 d >= len(a) 或 d 为负数的情况

优化运行时（嵌套循环和数组的浅拷贝）

Optimizing runtime (nested loop and shallow-Copy of Array)

python

runtime