什么是算法的时间复杂的和空间复杂度


为什么要知道时间复杂度和空间复杂度

我们学习算法的目的,就是为了解决程序的效率和内存的占用问题。如何让程序运行的更快,更省内存便是学习数据结构和算法的目的了。 那么,这里的“快”就是我们这里的时间复杂度,省内存便是空间复杂度。 只要学会了复杂度的分析,也就掌握了算法学习的精髓。

时间复杂度该如何分析呢?

时间复杂度就是我们算法中常说的大O(英文字母)。它表示的是代码或者算法的执行效率,粗略的说就是代码的执行时间,但实际上又不是一个具体的时间。 那么,该如何通过肉眼得到一段代码的执行时间呢? 让我们一起来估算一下下面这段代码的执行时间:

def func(n):
    sum = 0
    for i in range(n):
        sum = sum + i
    return sum

上面的这段代码计算的就是从0加到n的和。 我们假设每行代码的执行时间固定,那么这段代码的总执行时间T(n)是多少呢?

这里的T(n)表示的就是这段代码的执行时间。

经过观察:

  1. 第2行,第5行需要花费的时间分别为一个单位时间。
  2. 第3,4行则需要n个单位时间,这里取决n的大小。

尽管我们不知道,单位时间具体是多少,但是通过观察可以得到一个很重要的规律,所有代码的执行时间T(n)和每行代码的执行次数n成正比。 如果将代码执行次的总和数用f(n)表示,那么T(n)和f(n)通过大O来表示:T(n) = O(f(n))

这就是我们常说的大O时间复杂度表示法,简称时间复杂度。 我们通常通过以下的方法来计算时间复杂度:

  1. 只关注循环次数最多的一段代码 上面的那段代码中的2,5行并不会因为n的变化而改变运行时间,所以可以忽略,而循环中的代码的执行次数是受n的变化而改变的。 所以这段代码的时间复杂度就是O(n)
  2. 加法法则:总复杂度等于量级最大的那段代码的复杂度 我们分析如下代码:

    def func(n):
     sum_1 = 0
     for i in range(n):
         sum_1 = sum_1 + i
    
     sum_2 = 0
     for x in range(n):
         for j in range(n):
            sum_2 =  sum_2 + x * j
    
     return sum_1 + sum_2
    

    和之前说的一样,除了循环之外的,不受n的大小影响,所以可以忽略,那么第一个for循环的复杂度我们知道是O(n), 那么,第二个循环我们可以通过具体数字观察一下,其实是 n²。所以它的时间复杂度为O(n²)。 那么整段代码的复杂度我们就取其中最大的那个,即O(n²)。也就是说:总的时间复杂度就是量级最大的那段代码的时间复杂度。

  3. 乘法法则:嵌套代码的复杂度等于嵌套内外的复杂度的乘积 分析如下代码
    def func(n):
     sum = 0
     for i in range(n):
         sum = sum + f(i)
    def f(i):
     sum = 0
     for x in range(i):
         sum = sum + x
     return sum
    
    这段代码中,在第一个循环里面调用了两外的一个函数,而函数f()中也有循环 第一个循环的复杂度为O(n),第二个循环的复杂度也是O(n),但是第二个的循环是在第一个循环中调用的,因此整段代码的复杂度为: T(n) = T1(n) + T2(n) = O(n * n) = O(n²)

空间复杂度

如果理解了时间复杂度,其实空间复杂度就很好理解了。 我们看如下代码

def func(n):
   sum = 0
   num_list = []
   for i in range(n):
       num_list.add(i)

同样的sum = 0 并不会因为n的大小和受影响,它的内存始终不变。真正影响的是for循环,内存的大小取决于n的大小。 所以这段代码的空间复杂度就是O(n)