👨‍🎓作者简介：一位喜欢写作，计科专业大二菜鸟

🏡个人主页：starry陆离

🌌上期文章：『首期文章』

📚订阅专栏：『算法分析与设计』如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦

『算法导论』什么是算法？什么是程序？

1.什么是算法

算法(Algorithm)是指解决问题的方法或过程，它包含一系列步骤，用来将 输入数据转换成输出结果

算法具有以下性质：

• 输入：有零个或多个输入
  
• 输出：至少有一个输出
  
• 确定性：组成算法的每条指令清晰、无歧义
  
• 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限
  

2.“算法”的来源

算法(Algorithm) 一词来源于著名的波斯帝国 塔吉克族数学家、天文学家、地理学家—— 阿尔·花剌子模(Al-Khwarizmi)，其拉丁名为 阿尔戈利兹姆(Algorismus)

他是代数与算术的创立人，被誉为“代数之父”。“代数(Algebra)”源于他的一本书的 标题，而“算法(Algorism、Algorithm)”源 于他的拉丁文名

3.什么是程序

程序(Program)是算法用某种程序设计语言的具体实现

• 程序不一定满足有限性
  

这一点是算法和程序的最大区别，算法是有限的，但是程序是可能无限的；例如操作系统只要不关机就是一个无限期执行的程序

4.三种常用的描述算法的形式

自然语言

• 优点：通俗易懂
  
• 缺点：但缺乏直观性和简洁性，且易产生歧义。
  
• 举例： “南京市长江大桥”、“这个人连我都不认识”、“我曾经喜欢一个人，我现 在喜欢一个人”……
  

程序流程图

• 优点：描述算法形象、直观，容易理解，
  
• 绘制过程比较费时费力，难 以修改。
  

伪代码

• 优点：简单易懂，修改容易，易于转化为程序语言代码
  
• 缺点：伪代码格式难以规范
  

5.算法的好与坏

一个算法的好与坏一般是用时间复杂度和空间复杂度来衡量。

算法复杂性 = 算法所需要的计算机资源，用N、I 来表示算法要解决问题的规模和算法的输入，用C表示算法的复杂性，有：C =F(N,I)

算法的时间复杂性T(n)：如果问题的规模为n，在算法输入为I时算法所需的 时间资源为T(N,I) ，T(N,I)称为算法的时间复杂性

算法的空间复杂性S(n)：如果问题的规模为n，在算法输入为I时算法所需的 空间资源为S(N,I) ，S(N,I)称为算法的空间复杂性

6.算法复杂性的渐近性态

算法复杂性的渐近性态：对于F(N)，如果存在F’(N)，使得当N→∞时有： (F(N )-F’(N )) / F(N ) → 0 则F’(N)是F(N)当N→∞时的渐近性态

例：F(N)=3N2+4Nlog2N +7，求F’(N)

网络异常，图片无法展示

|

F’(N)的一个答案是3N2，

7.时间复杂性渐进表示法

设f(N)和g(N)是定义在正数集上的正函数。

O的定义：如果存在正的常数C和自然数N0，使得当N >= N0时有f(N) <= Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为 f(N)=O(g(N))，即f(N)的阶不高于g(N)的阶

例：

• 对所有N >=1时，3N <=4N，故3N=O(N)
  
• 对所有N>=1时，N+1024 <=1025N，故N+1024=O(N)
  
• 对所有N >=10时，2N²+11N-10 <=3N²，故2N²+11N-10=O(N² )
  
• 对所有N >=1时，N² <=N³，故N²=O(N³ )
  

练习题：对于f(n)=n，下列说法错误的是（显然选B）

A. f(n)=O(n) • B. f(n)=O(1/n) • C. f(n)=O(n² ) • D. f(n)=O(n³ )

Ω的定义：如果存在正的常数C和自然数N0，使得当N >= N0时有f(N) >= Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为 f(N)=Ω(g(N))，即f(N)的阶不低于g(N)的阶。

例：

• 1024n+1024 = Ω(n)
  
• n2+n+1 = Ω(n)
  
• 2n³+nlogn+1 = Ω(n² )
  

练习题：求下列函数的渐进表达式，用大O表示

• (1) 5n² + 10n =O(n²)

• (2) n + nlogn²=O(nlogn)

• (3) n² /100 + 3n =(O(n²))

• (4) 20 log3ⁿ =O(n)

• (5) 1/n² + 1 = O(1)

• (6) logn⁵ + n^1/2 = O(logn)

8.常见的算法复杂度的大O阶

O(1): 表示算法的运行时间为常量时间

O(logn): 二分查找等算法

O(n): 线性算法，例如线性查找

O(nlogn): 快速排序、归并排序等算法

O(n2 ): 对数组进行排序的简单算法，例如冒泡排序等

O(n3 ): 做两个n阶矩阵的乘法运算

O(2ⁿ ): 求具有n个元素集合的所有子集的算法

O(n!): 求具有n个元素的全排列的算法