《大话数据结构》学习笔记-day02-算法

算法:

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

一, 两种算法的比较

计算 1+2+3+4….+100 我们第一之间想到的写法是:

1
2
3
4
5
6
7

int sum = 0;
int n = 100;
for (int i = 1;i <= n; i++)
{
	sum = sum + i;
}
System.out.println(sum);

1.1 高斯算法

sum = 1+2+3+4+…+100

sum = 100+99+98+…+2+1

2xsum = 101+101+101+…+101+101

所以 sum = 5050

代码实现:

1
2
3

int i,sum = 0,n = 100
sum = (1 + n) * n / 2
println(sum)// 5050

​ 高斯算法相当于另一种求等差数列的算法,不仅仅可以用 1 加到100,就是 一千,一万,也就是瞬间的事,如果用刚才的程序,就要循环 一千,一万次

1.3 算法定义

如今普遍认可的对算法的定义事:

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

​ 为了解决某个 或 某类问题, 需要把指令表示成一定的操作序列,操作序列包括一组操作,每一个操作都完成特定的功能,这就是算法了

1.4 算法的特性

算法的五个基本特性: **输入,输出,有穷性,确定性 和 可行性**

1.4.1 输入输出

​ 算法具有零个或多个输入,大多数算法来说,输入参数都是必要的,但对于个别情况,比如打印Hello,World!这样的代码不需要任何输入参数,因此算法的输入可以是零个

​ 算法至少有一个或多个输出,算法一定需要输出的,不需要输出,用算法的意义是什么?输出的形式可以是打印输出,也可以是返回一个或多个值等..

1.4.2 有穷性

**有穷性: 指算法在执行完有限步骤之后,自动结束而不会出现死循环,并且每一个步骤在可接受的时间内完成**

​ 现实中经常写出死循环代码,这就是不满足穷性,这里的穷的概念并不是纯数学意义,而是在实际应用当中合理的,可以接受的 “有边界”,你说你写的算法,计算机需要运行二十年,一定会结束,它在数学意义上是有穷了,可是媳妇熬成婆了,算法意义就不大了

1.4.3 确定性

确定性: 算法的每一步骤具有确定的含义,不会出现二义性

​ 算法的每个步骤被精确定义而无歧义

1.4.4 可行性

可行性: 算法的每一步都必须是可行的,也就是说,每一步都能够通过执行有限次数完成

​ 意味着算法可以转换为程序上机运行,并得到正确结果

二, 算法设计的要求

​ 算法不是唯一的,同一个问题,可以有多个解决问题的算法,尽管算法不唯一,但是相对好的算法是存在的,那么什么是好的算法?

​ 起码要正确,如果正确都谈不上,还谈什么性能

2.1 正确性

​ 正确性: 算法的正确性是指算法至少应该具有输入,输出和加工处理无歧义性,能正确反映问题的需求,能够得到问题的正确答案

​ 好的算法是容易理解的

2.2 可读性

​ 可读性: 算法设计的另一目的是为了便于阅读,理解和交流

​ 如果可读性不好,时间长了可能自己都不知道再写些什么,可读性是算法(也包括实现它的代码) 好坏很重要的标志

2.3 健壮性

​ 健壮性: 但输入的数据不合法的时候,算法也能做出相关的处理,而不是产生异常或莫名其妙的结果

​ 比如输入的时间或者距离不应该是负数等

2.4 时间效率高,和存储量低

对于同一个问题,如果有多个算法能够解决:

时间效率上 > 执行时间最短的算法效率高,执行时间长的效率低

存储量 > 算法在执行的过程中需要最大的存储空间,主要指程序运行时所占用的内存或外部硬盘存储空间

​ 设计算法应尽量满足书简效率高,存储量低的需求

​ 综上,好的算法,应该具有 正确性,可读性,健壮性,高效率和低存储量的特征

三, 算法效率的度量方法

我们通过对算法的数据测试,利用计算机的计时功能,来计算不同算法的效率高低

3.1 事后统计方法

**事后统计方法:  这种方法主要是通过设计好的测试程序和数据,利用计算机计时,对不同算法编制的程序的运行时间进行比较,从而确定算法效率的高低**

这种方法有很大的缺陷:

• 需要花费时间和精力去编写程序,如果写出来的是很糟糕的算法,那就是浪费时间了
• 比较依赖计算机硬件和软件等环境因素,有时候会掩盖算法本身的优劣
• 测试的数据的大小,比如10个和100万个数据,数据的多少会影响算法的优势,有可能A算法计算小数据的时候比B快,有可能到了100万个数据的话,B又比A快

3.2 事前分析估算方法

​ 计算机前辈们为了对算法评判更加科学,研究了一种 事前分析估算的方法

​ 事前分析估算方法: 程序编制前,依据统计方法对算法进行估算

• 算法采用的策略 , 方法 (算法好坏的根本)

• 编译产生的代码质量 (软件来支持)

• 问题输入的规模

• 机器执行指令的速度 (硬件性能)

  ​ 程序的运行时间,依赖于算法的好坏和问题输入的规模,所谓问题输入规模是指输入量的多少

再来看看刚才的两个例子:

• 第一种算法

• 第二种算法:

​ 第一种算法执行了 1+(n+1) + n+1刺 = 2n+3 次;

​ 第二种算法是 1+1+1=3次

​ 两个算法其实是 n 次 与 1次的差距,算法的好坏显而易见

• 延伸一下

​ i 从 1 到 100 ,每次都让 j 循环 100 次, 而当中的 x++和 sum = sum + x;

​ 其实就是 1+2+3…+10000,也就是100²次,所以这个算法当中,循环部分的代码整体需要执行 n² (忽略循环体头尾的开销)次

​ 测试运行时间最可靠的方法就是计算对运行时间有小号的基本操作的执行次数,运行时间于这个计数成正比

​ 最终,在分析程序的运行时间时,最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤

​ 同样输入规模 n :

• 第一种算法 就是 1+2+3…+n, 那么这个问题的输入规模使得操作数量是f(n) = n, 100次同一段代码规模,是运算10次的10倍;
• 而第二种算法,无论n为多少,运行次数都为 1 ,即 f(n) = 1;
• 第三种,运算 100 次 是运算10次的100倍, 因为他是 f(n) = n²;

​ 我们在分析一个算法的运行时间时,重要的是把基本操作的数量与输入规模关联起来,即基本操作的数量必须表示成输入规模的函数

四, 函数的渐近增长

• (1) 判断算法A 和 算法B 哪个好,假设两个算法的输入规模都是 n

​ 算法A 要做 2n + 3 次操作,可以理解成先有一个 n 次循环,执行完成后,再有一个 n 次循环 , 最后有三次赋值或运算,共 2n+3次操作,

​ 算法B 要做 3n+1次操作, 请问它们谁更快

​ 准确来说,答案是不一定的

​ n = 1 时,算法A效率不如B (次数比算法B要多一次),而当 n=2时,两者效率相同;当 n>2时,算法A就开始优于算法B了,随着n增加,算法A比 B越来越好了(执行的次数比B要少),结论是算法A总体比B好

​ 此时我们给出这样的定义,输入规模n在没有限制的情况下,只要超过一个数值N,这个函数就总是大于另一个函数,我们称函数是渐近增长的

函数的渐近增长: 给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么,我们说f(n)的增长渐近快于 g(n)

​ 从中可以发现,随着 n 的增大,后面的+3 还是 +1 其实是不影响最终的算法变化的,例如算法A 与 算法B , 所以, 我们可以忽略这些加法常数,后面的例子会更加明显

• (2) 算法C 是 4n + 8, 算法D是 2n²+1 // n=3时,n²=9,9+9=18,18+1=19

​ 当 n <= 3 的时候,算法C要差于D (因为算法C次数比较多),但当 n>3后,算法C的优势越来越大于D了,后面更是远远胜过,而把后面常数去掉后,我们发现结果没有变化,甚至再观察发现,哪怕去掉与n相乘的常数,这样的结果也没发生改变, 算法C’的次数随着从n 的增长,还是远小于算法D’,也就是说,与最高次项相乘的常数并不重要

• (3) 算法E 是 2n² + 3n + 1, 算法F是 2n³ + 3n + 1

​ n = 1的时候, 算法E 与 算法F 的结果相同 , 但当 n>1后,算法E的优势就要开始优于算法F,随着n的增大,差异非常明显, 通过观察发现, 最高次项的指数大的,函数随着n的增长,结果也会变得增长的特别快

• (4) 算法 G 是 2n²,算法H 是 3n + 1 , 算法I 是2n² + 3n + 1

​ 根据这个例子,我们得出结论,判断一个算法的效率时,函数中的常数和其他次要项常常可以忽略,而更应该关注主项(最高阶项)的阶数

​ 判断一个算法好不好,通过前几个例子,可以对比这几个算法的渐近增长性,基本可以分析出:某个算法,随着n的增大,它会越来越优于另一算法,或越来越差于另一算法,这其实就是事前估算方法的理论依据,通过算法的时间复杂度来估算算法时间效率

五, 算法时间复杂度

5.1 算法时间复杂度定义

算法分析时,语句执行次数T(n) 是 关于问题规模 n 的函数,进而分析T(n) 随 n 的变化情况并确定T(n)的数量级,算法时间复杂度,也就是算法的时间量度,记作: T(n) = O(f(n)),他表示随问题规模n的增大,算法时间增长率和 f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度,其中 f(n)是问题规模n的某个函数

​ 用大写的 O() 来体现算法时间复杂度的记法,我们称为 大O记法

​ 一般来说,随着n的增大,T(n)增长最慢的算法成为最优算法

​ 非官方名称: O(1)常数阶 , O(n)线性阶 , O(n²)平方阶 等等..

5.2 推导大 O 阶方法

推导大O阶:

• 用常数 1 取代运行时间所有的加法常数

• 再修改后的运行次数函数中,只保留最高阶项

• 如果最高阶项存在且不是 1 , 则去除这个项相乘的常数

  得到的结果就是大O阶

5.3 常数阶

高斯算法:

1
2
3

int sum = 0,n=100; //执行一次
sum = (1+n)* n/2;//执行一次
print(sum)//执行一次

​ f(n) = 3, 根据推导大O阶的方法, 把 3 改为 1, 保留最高阶项时发现,它没有最高阶项,所以这个算法时间复杂度为 O(1)

​ 如果 sum = (1+n)* n/2;有10句:

1
2
3
4
5
6
7
8
9
10
11
12

int sum = 0,n=100; 	//执行一次
sum = (1+n)* n/2;//执行一次
sum = (1+n)* n/2;//执行一次
sum = (1+n)* n/2;//执行一次
sum = (1+n)* n/2;//执行一次
sum = (1+n)* n/2;//执行一次
sum = (1+n)* n/2;//执行一次
sum = (1+n)* n/2;//执行一次
sum = (1+n)* n/2;//执行一次
sum = (1+n)* n/2;//执行一次
sum = (1+n)* n/2;//执行一次
print(sum)			//执行一次

​ 时间复杂度还是 O(1) , 因为他俩的区别就是 3次 和 12次执行的差异,这种与问题的大小无关(n 的多少),执行时间恒定的算法,我们称之为具有 O(1)的时间复杂度,又叫常数阶

​ 注意: 不能计为 O(3),O(12)等其他任何数字,只能是 O(1)

5.4 线性阶

​ 线性阶循环结构要复杂很多,要确定某个算法的阶次,我们长长需要确定某个特定语句或某个语句集运行的次数,因此,我们要分析算法的复杂度,关键要分析循环结构的运行情况

​ O(n)的算法:

1
2
3
4

int i;
for (i = 0; i < n; i++){
	// 时间复杂度为 O(1)的程序步骤序列
}

5.5 对数阶

​ 由于每次 count 乘以2之后,就距离n更近了一分,也就是说,有多少个 2 相乘后大于 n,则退出循环,由 2^x = n 得到 x = log^2 n,所以这个算法时间复杂度为 O(logn)

5.6 平方阶

​ 对于外循环,内循环这个时间复杂度为O(n)的语句,再循环n次,所有这段代码时间复杂度为O(n²)

​ 如果外循环的循环次数改为了 m,时间复杂度就变为了O(m ✖ n)

1
2
3
4

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

​ 总结出: 循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数

​ 对于方法调用的时间复杂度该如何分析:

1
2
3
4
5

int i,j;
for (i = 0; i < n; i++)
{
    function(i)
}

​ 上面代码调用了 一个函数 function

1
2
3
4

void function (int count)
{
	print(count)
}

​ 函数体就是打印这个参数,其实这很好理解,function 函数的时间浮躁度是 O(1),所以整体的时间复杂度为O(n)

​ 假如 function 是下面这样的:

1
2
3
4
5
6
7
8

void function(int count)
{
	int j;
	for(j = count; j < n; j++)
	{
		// 时间复杂度为 O(1)的程序步骤序列
	}
}

​ 这和刚才的例子一样,只不过把嵌套内循环放到了函数中,所以最终的时间复杂度为O(n²)

​ 下面这段相对复杂的语句:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

n++;					// 执行次数为 1
function(n);			// 执行次数为 n
int i,j					
for (i = 0;i < n; i++)	// 执行次数为 n²
   {
       function(i)
   }
for (i = 0;i < n; j++)	// 执行次数为 n(n+1)/2 
   {
       for ( j = i; j < n; j++)
       {
           // 时间复杂度为O(1)的程序步骤序列
       }
   }

​ 它的执行次数:

​ 根据推导大O阶的方法,最终这段代码的时间复杂度为O(n²)

六, 常见的时间复杂度

七, 最坏情况与平均情况

​ 如果我们想要查找 n 个元素的数组中某个数字,最好的情况第一个数字就是,那么算法的时间复杂度O(1),但也有可能这个数字在最后一个位置上待着,那么算法的时间复杂度就是O(n),这是最坏的一种情况了

​ 最坏情况运行时间: 是一种保证,那就是运行时间不会再坏了,在应用中,这是一种最重要的需求,通常,除非特别指定,我们提到的运行时间都是基于最坏情况的运行时间

​ 平均运行时间: 是所有情况中最有意义的,因为它是期望的运行时间

但是在没有特殊说明的情况下,都是指最坏时间复杂度

八, 算法空间复杂度

​ 算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作 :

S(n)= O(f(n)), 其中 ,n为问题的规模,f(n)为语句关于 n 所占存储空间的函数

​ 一般情况下,一个程序执行时,除了需要存储程序本身的指令,常数,变量和输入数据外,还需要存储对数据操作的存储单元,若输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在时间时所需的辅助单元即可,若算法执行时所需的辅助空间相对于输入数据量而言是个常数,则称此算法为原地工作,空间复杂度为 O(1)

​ 通常我们都用 “时间复杂度” 来指运行时间的需求,使用”空间复杂度”指空间需求,当不用限定词地使用”复杂度”时,通常都是指时间复杂度

九, 总结

​ 数据结构与算法关系是相互依赖不可分割的

​ 算法的定义:

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

• 算法的特性: 有穷性,确定性,可行性,输入,输出
• 算法的设计的要求: 正确性,可读性,健壮性,高效率和低存储量需求
• 算法特性与算法设计容易混,需要对比记忆
• 算法的度量方法: 事后统计方法(不科学,不准确),事前分析估算方法

​ 在说如何用事前分析估算方法以前,我们先给出了函数渐近增长的定义

• 函数的渐近增长 : 给定两个函数 f(n) ,g(n), 如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么,我们说 f(n) 的增长渐近快于g(n), 判断算法的好不好,只通过少量的数据是不能做出准确判断的,如果我们可以对比算法的关键执行次数函数的渐近增长行,基本可以分析出:某个算法,随着问题规模n的扩大,越来越优于另一个算法,或者越来越差于另一个算法

  ​

  然后给出了算法时间复杂度的定义和推导大O阶的步骤

  推导大O阶:

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

  得到的结果就是大O阶

  通过这个步骤,我们可以在得到算法的运行次数表达式后,很快得到它的时间复杂度,即大O阶,其实推导大O阶很容易,但如何得到运行次数的表达式却是需要数学功底的

  常见时间复杂度所耗时间的大小排列:

  

  最后,给出了算法最坏情况和平均情况的概念,以及空间复杂度的概念