算法的复杂度定义

Category: 算法
Date:

Content:

不同算法的优劣，通过以下两个维度来衡量：

  • 时间复杂度：是指执行当前算法所消耗的时间
  • 空间复杂度：是指执行当前算法需要占用多少内存空间


时间复杂度：

定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数。定性描述该算法的运行时间。

通常使用 大O符号表示法来衡量其时间复杂度，，可看作是算法的渐进时间复杂度。

公式：T(n) = O (f(n))。

T(n)表示随输入规模n的增大，算法执行时间的增长率。其中f(n) 表示每行代码执行次数之和。

以下面例子为例：

for(i=1; i<=n; i++)             #1
{
   j = i;                       #n
   j++;                         #n
}

假设每行代码的执行时间都是一样的，上面的代码总共执行了1+2n个时间单位，即T(n) = O (1+2n)。可以看出算法消耗的时间是随着n的变化而变化的，当n足够大时，即循环次数非常多时，常量1和倍数2的作用已经微乎其微，所以该代码实际为T(n) = O (n)，即时间复杂度为 O (n)。

判断一个算法的时间复杂度时，假设n无限大，加法常数项和其他次要项（譬如系数，最高次项相乘的常数）常常可以忽略，最高阶项的阶数的影响通常是最大的。


执行时间的定义

最坏情况：结果在最后的时候才出现。

平均情况：期望的运行时间。


通常情况下，以最极限的情况，即最坏情况作为标准。才能有效评估算法的复杂度。

所以，以下的执行时间均是指最坏情况的运行时间。


推导大O阶方法

  1. 用常数1取代运行时间中的所有加法常数。
  2. 在修改后的运行次数函数中，只保留最高阶项。
  3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数。


常见的时间复杂度量级

  • 常数阶O(1)
  • 对数阶O(logN)
  • 线性阶O(n)
  • 线性对数阶O(nlogN)
  • 平方阶O(n^2^)
  • 立方阶O(n^3^)
  • K次方阶O(n^k^)
  • 指数阶O(2^n^)
  • 阶乘O(n!)

从上至下依次的时间复杂度越来越大，执行的效率越来越低。最优算法是指随着输入规模n的增大，T(n)的增长率最慢。


具体的时间复杂度分析

1. 常数阶O(1)：

sum = 0
n =1000
print("1")
print("1")
print("1")
print("1")
sum = (1+n)*n/2

主要看与输入规模有关的语句，这里是sum语句。无论n为多少，执行时间不会随着n的增大而增大，永远只是执行一次就完成。其他的赋值和打印可忽略。


2. 线性阶O(n)：

for(i=1; i<=n; i++)
{
   j = i;
}

在for循环里面，循环的次数取决于n的大小，即时间复杂度为 O (n)。


3. 对数阶O(logN)：

i = 1;
while(i<n)              
{
    i = i * 2;
}

在while循环里面，每次都将i乘以 2，每乘一次，i距离 n 就越近。假设循环x次之后，i大于n了，该循环就退出。也就是说 2 的 x 次方等于 n， x = log~2~n，即时间复杂度为 O (logn)。

通常在二分法中见到


4. 线性对数阶O(nlogN)

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

将时间复杂度为O(logn)的代码循环N遍，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。


5. 平方阶O(n^2^)、O(m*n)

将时间复杂度为O(n)的代码循环N遍（嵌套循环），那么它的时间复杂度就是 O(n) * O(n)，也就是O(n^2^)。循环的时间复杂度等于循环体的复杂度乘以该循环运行次数。

普通例子：

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

如果将时间复杂度为O(n)的代码循环M遍，那么它的时间复杂度就是 O(m) * O(n)，也就是O(m*n)。

for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

特殊的循环嵌套，内循环体随着外循环的条件递增而减少。

for(i=0; i<n; x++)
{
   for(j=i; l<n; i++)
    {
       ...
    }
}

#推导过程：
当i=0时，内循环执行了n次，当i=1时，执行了n-1次...当i=n-1时，执行了一次。
n+(n-1)+(n-2)+...+1=n(n+1)/2≈n²


6. 指数阶O(2^n^)

def func(n):
    if n <=1：
        return 1
    else:
        return max(func(n-1),func(n-2))

随着n的增加，计算的次数呈指数性增长。在动态规划中很常见，譬如旅行背包问题。


7. 阶乘O(n!)

def fact(n):
    if n==1:
        return 1
    return n * fact(n - 1)


空间复杂度：

是一个算法在运行中临时占用存储空间大小的量度。不是实际计算程序占用的空间。

公式：S(n) = O (f(n))

执行时所需存储空间包括以下两部分：

固定部分：语言本身的数据结构，指令的空间大小。

变化部分：分配变量，递归栈所需空间，存储结果等等。

因为不同语言结构的固定部分必然使用不同的存储空间，抛开计算机系统差异和编程语言的差异，其算法的空间复杂度主要涉及的就是变化部分。


常见的空间复杂度量级

  • 常数阶O(1)
  • 线性阶O(n)
  • 平方阶O(n^2^)


具体的空间复杂度分析

1. 常数阶O(1)：

sum = 0
n =1000
sum = (1+n)*n/2

与时间复杂度类同，已创建的变量的存储空间不会随着n的变化而变化，因此它的空间复杂度 S(n) = O(1)。


2. 线性阶O(n)：

sum = []
n =1000
for i in range(n):
    s.append(i)

与常数阶不同，这里创建了一个数组变量，其内存空间是会随着n的增大而增大，因此它的空间复杂度 S(n) = O(n)。


3. 平方阶O(n^2^)：

sum = []
n =1000
for i in range(n):
    for j in i:
    s.append(j)

由于有内循环，而且该内循环的次数与n相关，所以其数组的内存空间是会随着n的增大而增大，因此它的空间复杂度 S(n) = O(n^2^)。


4. 指数阶O(2^n^)：

def dfs(digits, d, l, cur, ans):
    if l == len(digits):
        if l > 0: ans.append("".join(cur))
        return

for c in d[ord(digits[l]) - ord('0')]:
    cur[l] = c
    dfs(digits, d, l + 1, cur, ans)

d = [" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv","wxyz"]
cur = [' ' for _ in range(len(digits))]
ans = []
dfs(digits, d, 0, cur, ans)
return ans

这个例子是手机的按键点击排列组合。按下若干个按键，输出由这些按键所拼接的所有字符串。

对于绝大多数的按键来说，一个按键会出现3个结果。但最后一个按键的结果是4个，所以按照最坏情况来统计，就必须得假设其底数为4。因此，它的空间复杂度 S(n) = O(4^n^)。


There are 0 comments