1.算法定义



算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。

通俗来说,数据结构是指一组数据的存储结构,而算法就是操作数据的一组方法。就好比图书馆藏书籍,为了方便查找,通常都会分门别类地整理放在特定的地方,这些书籍的结构就是存储结构。当我们需要查找书的时候,我们是要按类别来查找呢,还是一本一本地找?或者按书本编号来查找?这个就是对数据存储的操作。所以说这些查找的方法都是算法。

算法的五个基本特性:


  1. 输入:每个算法都有零个或多个输入
  2. 输出:算法一定会有输出,要不这个算法毫无意义
  3. 有穷性:指算法在执行有限的步骤后能自动结束,不会陷入死循环。并且每个步骤都需要在可接受的时间内完成
  4. 确定性:算法的每个步骤都需要有明确的意义
  5. 可行性:算法的每一步都能够通过执行有限次数完成

    对算法设计的五个要求

  6. 正确性:指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案
  7. 可读性:设计的算法便于阅读、理解和交流
  8. 健壮性:当输入非法数据时,算法也能做出相应的处理,而不是产生异常或者有莫名其妙的结果
  9. 时间效率高:也就是等等下面详细说的时间复杂度要小。
  10. 存储量低:就是空间复杂度,追求时间少的同时,也尽可能追求需要消耗的内存少点。


2.度量算法的执行时间


事后统计方法



就是使用大量的测试数据进行对算法的测试,进而对不同的算法运行时间进行比较来确定算法效率的高低。

这样子并不好,一是测试结果非常依赖于测试环境,二是测试结果需要大规模的数据进行测试,非常浪费人力物力。非常不推荐使用这种方法来进行度量。

大 O 复杂度的表示法



通过对算法步骤实现代码的运行次数来度量算法的执行时间,随着代码的运行次数越少,其执行时间必定会越少,就比如下面这个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# include<stdio.h>
# include<stdlib.h>

int main(void)
{
int sum = 0;
int i;
for(i = 0; i <= 100; i++)
{
sum = sum + i;
}
printf("sum=%d\n", sum);
system("pause");
return 0;
}

复杂度分析

如上图所示,这段代码的时间复杂度就是 2n+ 5,当 n 很大时,这个公式中的低阶、常量和系数都是可以忽略不计的,也就是说上面程序的复杂度就是 n,记作 O(n)。

3.时间复杂度的分析

只关注循环执行次数最多的一段代码

因为大 O 这种复杂度分析只关注最大阶的量级,会忽略掉低阶、常量和系数,所以在对时间复杂度的分析时,可以直接对循环次数最多的代码进行分析即可。

1
2
3
4
5
6
7
int i = 1;
while(i < 100)
{
i = i * 2;
}
system("pause");
return 0;



根据方法我们只看循环部分即可,这个的分析方法可以先设 x 为代码执行步数,当 i 大于等于 100 时会退出循环,就是有 2 的 x 次方 等于 n(100),可以推得 x = log2n ,最后去掉常量,一般写成 O(logn).

加法法则



就是总复杂度等于量级最大得那段代码的复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int i, j;
int sum = 0;
for(i = 0; i < 100; i++)
{
sum = sum + i;
}

for(j = 0; j < 1000; j++)
{
sum = sum + j;
}

for(i = 0; i < 1000; i++)
{
for(j = 0; j < 1000; j++)
{
sum = sum + i;
}
}
system("pause");
return 0;



这个前面的两个循环都不如第三个嵌套循环量级大,就可以直接分析第三个循环的时间复杂度即可,所以该时间复杂度就是 O(n2)

3.乘法法则



嵌套代码的时间复杂度等于嵌套内外代码复杂度的乘积。

嵌套可以是循环嵌套,也可以是函数内部嵌套另一个函数。

他们的时间复杂度都是外部嵌套的时间复杂度 乘于 内部嵌套代码的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int f1(int n)
{
int i = 0;
int sum = 0;
for(; i < n; i ++)
{
sum = sum + f2(i);
}
return sum;
}

int f2(int n)
{
int i = 0;
int sum = 0;
while(i < n);
sum = sum * 2;
return sum;
}

上面的 f1 函数的时间复杂度就是等于 f1的循环代码的时间复杂度 乘于 f2 的时间复杂度, 也就是 O(n*logn)


4.常见的时间复杂度


  • 常数阶O(1),
  • 对数阶O(log n),
  • 3线性阶O(n),
  • 线性对数阶O(n log n),
  • 平方阶O(n^2),
  • 立方阶O(n^3)
  • k次方阶O(n^K),
  • 指数阶O(2^n)。


    消耗时间从小到大排序为: O(1) < (log n) < (n) < O(n log n) < (n^2) < O(n^3) < O(n^3) < O(n^K) < O(2^n)