什么是时间复杂度和空间复杂度

当我们在编写算法时,我们需要考虑两个方面的问题:时间和空间。时间复杂度和空间复杂度是比较重要的衡量标准,它们可以帮助我们优化算法,提高程序的运行效率。

时间复杂度(Time complexity)

时间复杂度通常用大O表示法(O(n))衡量算法运行时间的长短。它表示随着输入规模的增加,算法执行时间的增速。时间复杂度的量级可分为:常数阶(O(1))、对数阶(O(log n))、线性阶(O(n))、线性对数阶(O(n log n))、平方阶(O(n^2))、立方阶(O(n^3))、k次方阶(O(n^k))、指数阶(O(2^n))。

在实际应用中,我们通常选择时间复杂度尽可能低的算法。下面是两个示例,分别对比不同时间复杂度的算法:

例1:计算斐波那契数列的第n项,可以用递归实现,代码如下:

def fib(n):
    if n<=0:
        return 0
    elif n==1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

该算法的时间复杂度为O(2^n),随着n的增大,运行时间呈指数级增长,速度非常慢。

而通过循环方式实现斐波那契数列的计算,代码如下:

def fib(n):
    if n<=0:
        return 0
    elif n==1:
        return 1
    else:
        a,b = 0,1
        for i in range(n-1):
            a,b = b,a+b
        return b

该算法的时间复杂度为O(n), 运行时间随着n的增加而增加,但是增长速度大大缓慢。

通过对比两个算法的时间复杂度,我们可以看到,算法2的时间复杂度明显低于算法1,也就是说,在计算斐波那契数列时,算法2更加优秀。

空间复杂度(Space complexity)

空间复杂度也是一个非常重要的度量标准。它表示一个算法在运行过程中所需要的内存空间。通常来说,空间复杂度也可以用大O表示法表示。

空间复杂度高的算法将会占用更多的内存。我们需要尽量避免使用空间复杂度高的算法。

以下是两个示例,分别说明了如何优化空间复杂度。

例2:给定一个整数数组nums,将数组中所有的0移动到数组的末尾,同时保持其他元素的相对顺序不变。

def moveZeroes(nums):
    zero_count = nums.count(0) 
    nums[:]= [i for i in nums if i != 0]
    nums += [0 for i in range(zero_count)]

在该示例中,我们使用了两个列表来存储数据,因此空间复杂度较高。一个更好的实现是直接在原始数组中进行操作,代码如下:

def moveZeroes(nums):
    length = len(nums)
    last_zero_ptr = 0
    for i in range(length):
        if nums[i]!=0:
            nums[last_zero_ptr] = nums[i]
            last_zero_ptr += 1
    for i in range(last_zero_ptr, length):
        nums[i] = 0

该算法只使用了常数的额外空间,因此空间复杂度远低于第一种不优化的算法。

综上所述,时间和空间复杂度是我们衡量算法好坏的两个重要标准。在实际应用中,我们应该根据需要合理选择算法,并尽可能优化算法以提高效率。