程序员的数学归纳法第四章

1. 程序员的数学的作者目录

第1章 0 的故事
——无即是有
本章学习内容 2
小学一年级的回忆 2
10 进制计数法3
什么是10 进制计数法3
分解25033
2 进制计数法4
什么是2 进制计数法4
分解11005
基数转换 6
计算机中为什么采用2 进制计数法8
按位计数法10
什么是按位计数法10
不使用按位计数法的罗马数字11
指数法则12
10 的0 次方是什么12
10-1 是什么13
规则的扩展14
对20 进行思考14
2-1 是什么15
0 所起的作用16
0 的作用：占位16
0 的作用：统一标准，简化规则16
日常生活中的017
人类的极限和构造的发现18
重温历史进程18
为了超越人类的极限19
本章小结20
第2章 逻辑
——真与假的二元世界
本章学习内容22
为何逻辑如此重要22
逻辑是消除歧义的工具22
致对逻辑持否定意见的读者23
乘车费用问题——兼顾完整性和排他性 23
车费规则23
命题及其真假24
有没有“遗漏”24
有没有“重复”25
画一根数轴辅助思考26
注意边界值28
兼顾完整性和排他性28
使用if 语句分解问题28
逻辑的基本是两个分支29
建立复杂命题30
逻辑非——不是A30
逻辑与—— A 并且B32
逻辑或—— A 或者B34
异或—— A 或者B（但不都满足）37
相等—— A 和B 等39
蕴涵——若A则B40
囊括所有了吗45
德?摩根定律46
德?摩根定律是什么46
对偶性47
卡诺图48
二灯游戏48
首先借助逻辑表达式进行思考49
学习使用卡诺图50
三灯游戏52
包含未定义的逻辑54
带条件的逻辑与（&&）55
带条件的逻辑或（||）57
三值逻辑中的否定（！）58
三值逻辑的德?摩根定律58
囊括所有了吗59
本章小结60
第3 章 余数
——周期性和分组
本章学习内容64
星期数的思考题（1）64
思考题(100天以后是星期几)64
思考题答案64
运用余数思考65
余数的力量——将较大的数字除一次就能分组65
星期数的思考题（2）66
思考题(10100 天以后是星期几)66
提示：可以直接计算吗67
思考题答案67
发现规律68
直观地把握规律68
乘方的思考题70
思考题70
提示：通过试算找出规律70
思考题答案70
回顾：规律和余数的关系71
通过黑白棋通信71
思考题71
提示73
思考题答案73
奇偶校验73
奇偶校验位将数字分为两个集合74
寻找恋人的思考题74
思考题(寻找恋人)74
提示：先试算较小的数74
思考题答案75
回顾75
铺设草席的思考题77
思考题（在房间里铺设草席）77
提示：先计算一下草席数77
思考题答案78
回顾78
一笔画的思考题79
思考题（哥尼斯堡七桥问题）79
提示：试算一下80
提示：考虑简化一下81
提示：考虑入口和出口82
思考题答案82
奇偶校验85
本章小结86
第4 章 数学归纳法
——如何征服无穷数列
本章学习内容88
高斯求和88
思考题（存钱罐里的钱）88
思考一下89
小高斯的解答89
讨论一下小高斯的解答89
归纳91
数学归纳法—— 如何征服无穷数列91
0以上的整数的断言92
高斯的断言93
什么是数学归纳法93
试着征服无穷数列94
用数学归纳法证明高斯的断言95
求出奇数的和 —— 数学归纳法实例96
奇数的和96
通过数学归纳法证明97
图形化说明98
黑白棋思考题 —— 错误的数学归纳法99
思考题（黑白棋子的颜色）99
提示：不要为图所惑100
思考题答案 100
编程和数学归纳法101
通过循环表示数学归纳法101
循环不变式 103
本章小结107
第5章 排列组合
——解决计数问题的方法
本章学习内容110
计数——与整数的对应关系110
何谓计数110
注意“遗漏”和“重复”111
植树问题——不要忘记0111
植树问题思考题111
加法法则115
加法法则115
乘法法则117
乘法法则117
置换121
置换121
归纳一下122
思考题（扑克牌的摆法）123
排列125
排列125
归纳一下126
树形图——能够认清本质吗128
组合130
组合130
归纳一下131
置换、排列、组合的关系132
思考题练习 134
重复组合134
也要善于运用逻辑136
本章小结139
第6章 递归
——自己定义自己
本章学习内容142
汉诺塔142
思考题（汉诺塔）142
提示：先从小汉诺塔着手143
思考题答案 146
求出解析式 148
解出汉诺塔的程序149
找出递归结构150
再谈阶乘151
阶乘的递归定义152
思考题（和的定义）153
递归和归纳 153
斐波那契数列154
思考题（不断繁殖的动物）154
斐波那契数列157
帕斯卡三角形159
什么是帕斯卡三角形159
递归定义组合数162
组合的数学理论解释163
递归图形165
以递归形式画树165
实际作图166
谢尔平斯基三角形167
本章小结168
第7章 指数爆炸
——如何解决复杂问题
本章学习内容172
什么是指数爆炸 172
思考题（折纸问题）172
指数爆炸175
倍数游戏——指数爆炸引发的难题176
程序的设置选项176
不能认为是“有限的”就不假思索178
二分法查找——利用指数爆炸进行查找178
寻找犯人的思考题178
提示：先思考人数较少的情况179
思考题答案 180
找出递归结构以及递推公式181
二分法查找和指数爆炸183
对数——掌握指数爆炸的工具184
什么是对数 184
对数和乘方的关系184
以2为底的对数186
以2为底的对数练习186
对数图表187
指数法则和对数188
对数和计算尺190
密码——利用指数爆炸加密193
暴力破解法 193
字长和安全性的关系193
如何处理指数爆炸195
理解问题空间的大小195
四种处理方法195
本章小结196
第8章 不可解问题
——不可解的数、无法编写的程序
本章学习内容200
反证法200
什么是反证法200
质数思考题 202
反证法的注意事项203
可数203
什么是可数 203
可数集合的例子204
有没有不可数的集合206
对角论证法 207
所有整数数列的集合是不可数的207
所有实数的集合是不可数的211
所有函数的集合也是不可数的212
不可解问题 213
什么是不可解问题213
存在不可解问题214
思考题 215
停机问题215
停机216
处理程序的程序217
什么是停机问题217
停机问题的证明219
写给尚未理解的读者222
不可解问题有很多223
本章小结224
第9章 什么是程序员的数学
——总结篇
本章学习内容226
何为解决问题229
认清模式，进行抽象化229
由不擅长催生出的智慧229
幻想法则230
程序员的数学231

2. 一个算法的时间复杂度和其空间复杂度有何关系

一个算法的时间复杂度和其空间复杂度的关系可这样理解。

一个算法要做高效率低存储是很困难的，也就是说，算法的时间复杂度小，可能需要较大的空间复杂度。反之亦然。也可以说，通过空间换得时间。

算法的时间复杂度和空间复杂度可以同时很大，也可以同时很小。如T(n)=O(n)且S(n)=O(1)的情况比如一个for(i=0;i<N;i++)，若循环体中为一个与问题规模无关的变量变化，则其S(n)=O(1)，而T(n)=O(n)是随着N的变化而变化的，这时可以说时间复杂度较小而空间复杂度很小。

(2)程序员的数学归纳法第四章扩展阅读：

一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表示开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的形式给出。

3. 程序员的数学-读书笔记

计数法分为 按位计数法 和 罗马计数法
按位计数法常用的有2进制、8进制、10进制、16进制等几种。

理论上多少进制在数学上都可以存在，玛雅人用20进制，巴比伦人用10进制和60进制的混合计数法。玛雅人20进制可能是和手脚趾加起来的数量有关。巴比伦人采用60进制也可能是因为记录数字的黏土版比较难记录文字记号，为了在大数的书写上少占位便采用了60进制。
从这一点来看，环境对文明和文化的形成真的是有决定性的影响。假如巴比伦人掌握了造纸术或者在竹子上书写文字的话，60进制这种违反人类天性的计数方法一定不会出现。话说，汉莫拉比法典就是写在黑色的玄武岩上的。能够记录的文字也就屈指可数吧。

作者提到了其实人也是可以采用2进制计数法的，可是同样大小的数字用2进制书写起来位数太多，一来书写不方便，二来计算时易发生马虎出现错误。而10进制的数天生就是顺应人类人性的，即使是幼儿也可以通过数手指头的方式来计数。
相反对于计算机的物理构造来讲，0代表开关断开，1代表开关连接，这种二极管的物理限制正好决定了计算机较为适用2进制。不过如果你想做出一个10进制的计算机也不是没有可能的。

这一章比较有趣的是罗马计数法，我以前也没有接触过超过20的罗马数字，也不知道罗马数字各个数位上的数字相加之和为数字本身所代表的量。例如：

反观阿拉伯数字

由此引发作者在两个程序领域上的思考：

关键词：真值表、文氏图、逻辑表达式、卡诺图、三值逻辑、完整性、排他性

- 能够判断对错的陈述句叫做命题（proposition）

逻辑非 --不是A

逆命题

逆否命题

德摩根定律

卡诺图 （二灯游戏、三灯游戏引出）

未定义逻辑（undefined）

三值逻辑的德摩根定律

本章探讨的是通过余数来解决存在规律、周期性的问题。通过规律和周期性的重复，将大问题简化成容易解决的小问题。

首先作者通过解决星期几问题，引入了余数的思考概念。

上面的问题在 大问题通过余数规律简化为小问题 这个方法上表现的还不明显，于是引入了第三个问题：1234567^7654321的个位数是多少。

以上三个问题是小学奥赛便涉及到的问题，然而其思想在解决真实面对的复杂问题或具象的实际问题时却很好用。

将一个数字除以2，他的余数应该为0或者1二者之一。我们也可以叫 奇偶问题 。
书中有几个案例：

这样分析过来就很好解决七桥问题，确定每个点所连接的桥的点数，与上述结论做对比。
A点为3，B点为，C点为3，D点为3.
由此可以得出七桥问题不可能实现。这个问题的解决也是通过奇偶性来解决的。

作者举了高斯求和的故事来讲如何用数学归纳法来解决无穷数列的求和问题。
两个小例子便是从0开始到N的和，以及1开始的奇数和。

数学归纳法 是证明[ 有关整数的断言对于0以上的所有整数（0,1,2...）是否成立 ]所用的方法。
证明方法归结为两歩：

根据上述方法，假若某个假设成立，那么P(0)成立，因为P(0)成立，所以P(0+1)即P(1)也成立。反复如此，对于无穷数列遵守这个规律的证明，就像多米诺骨牌，推到第一个，后面的都会按照第一个的规则倒下去。

然而要避免整个证明出错，就要重视第二个步骤，也就是归纳。归纳在证明时一定要考虑 是否在所有定义条件下均成立 ，尤其要注意的是在P(0)的条件下是否实现。

课后对话很有意思：

计数是人类每天生活都要运用的方法。
计数的关键就在于 注意“遗漏”和“重复”
例如：

综上，在计数时要发现事物的规则。
要 认清计数对象的本质
要 认清计数对象的本质
要 认清计数对象的本质
重要的事情说三遍。

将计数对象进行 归纳总结 ，使其作为普通规则来掌握。这样一般不容易出错。

接下来，作者在 加法法则 里写到：

乘法法则 的概念比较有意思。

接下来，本章提到了置换、排列、组合3个概念。以下是几个小例子。

最后提到的 重复组合 里的思考问题比较有趣。

解答的思想是：

这是一种典型的将复杂问题简单化，并规律化的解答方法。

最后还是要强调下：
要 认清计数对象的本质

递归与归纳的区别

归纳（inctive） 是从个别性前提推出一般性结论。

本质上都是 将复杂问题简化 ，但方向不同。
个人理解是

递归是发现第n项和前一两项之间的关系，实证确定后，往回不断递推的一种个别性结论。
即这个结论不是在n为任何自然数时都成立的。需要注意n为0和1的两项。

通过递归解决问题的线路是： 找到递归结构——建立递推公式——找到解析式（只带n的式子） ，如果不能以解析式的方式描述递归结构，也可以用递推公式的方法描述。如下图所示的汉诺塔的递推公式：（它也可以描述成解析式的方式）

归纳所谓的个别性前提是指

斐波那契数列就是运用了递归的思想。通过研究和思考复杂问题，抓住事务本质，得到f(n)=f(n-1)+f(n-2)

所以当我们想要用递归的方法解决问题时，注意思考第n元素与前后元素的关系。由一个点推开，成一条贯穿始终的线。

利用帕斯卡三角形来研究Cnk=Cn-1(k-1) + Cn-1k的思考方式另辟蹊径。将两个加数假设成组合问题里含一个元素和不含那个元素的两个情况。从而证明了式子。利用的便是组合的数学分析法。（这句话组合的意思不是数学意义上的）。

所以以上将复杂问题简化的方法是递归解法之一，是为了在复杂问题中找到隐含的递归结构。其思路是：

通过思考一张1mm的纸，折多少次能够有地月距离那么厚，作者引出指数的概念。

这一章的内容比较简单，对于 指数爆炸 大家应该都不陌生。而 对数 估计也很熟悉。之前接触到的汉诺塔问题的解析式和斐波那契数列都属于指数的范畴。

然而在解决 测试所有设定选项的程序时，检查次数也是一个指数问题 。所以我们应该如何轻松的解决这类问题呢？

利用二分法查找

利用二分法，先询问最中间的人，如果在左边，就继续在左边的范围内重复此项方法，直到找到罪犯。这便被称为 2分法 。他和汉诺塔的解析式如出一辙，可以利用指数原理经过很少的步骤便可找到目标。

二分法本身也是 递归结构 ，经过n次询问，可以在2^n-1人中确定目标。每判断一次就可以查找近一半的对象。
二分法需要注意的是，所有元素一定要 按顺序排列 ，这点至关重要。

指数思想也被用于加密的实现中。因为每多加密一位，暴力破解就需要指数次的运算能力的提升。原则上有限时间里根本不可能破解。指数以其数字的巨大增长能力在加密领域有基本性的作用。

对于指数问题的解决方法，主要有4种，但均不太容易应付规模大的数字。

作为指数函数的逆函数，文章涉及了对数。同时也简单介绍了古代科学家用过的计算尺。

无穷可以分为 可数无穷 和 不可数无穷 。
所谓 可数无穷 是指 可以按照一定的规律或者表达方式来表达 。
即集合中所有元素都与正整数一一对应。如果每一个元素都可以与1.2.3....等数字对应，也就是说可以按规律表达出来就是可数无穷。
例如：

所以有不可数的集合吗？
此时运用到了 对角论证法 和 反证法（也叫归谬法）
假设我们要证明 所有整数数列的集合是不可数的 ，那么反证就是 假设所有整数数列的集合是可数的 ，此处是运用的反证法。
现在我们按下图的方式来列出所有整数数列，编号为k的整数列在表的k行。

如果按照图中第k行的第k个元素ak单独组出一组数列{a1,a2,a3......}的话，他也是应该包含在所有整数数列里的，然而并没有，他是游离在所有整数数列之外的。此处得出矛盾，说明命题错误，命题 所有整数数列的集合是不可数的 为真。此方法被称为 对角论证法
除此之外
-所有实数的集合是不可数的
-所有函数的集合也是不可数的

随后书中讨论到了不可解的问题
对于不可解的问题的定义是

事实上，不能写成程序的函数是存在的。
有些函数不能用文字表达，而且要写成程序的函数必须 严谨定义确切和文字表达 两个概念。

停机问题
不可解问题的一例。定义是

有限时间并不指时间长短，而是指无论耗时多长，只要能有终止的一刻就好。
事实上，程序本身并不能判断某一程序是否可以在有限时间内结束运行
所以停机问题也是 不可解问题 之一。

这一章是对之前8章的回顾和总结。

前几章作者分别对 0的意义、逻辑、余数、数学归纳、排列组合、递归、指数爆炸、不可解问题 进行了简单的介绍和探讨。其实所有的章节最后都是在引领读者产生如何解决问题的思考。

1.认清模式，进行抽象化

2.由不擅长催生出的智慧

3.幻想法则

本书比较适合作为第一本接触算法的书籍。目前开始在上 Khan的Algorithms ，9月份跟上 coursera的Algorithms Part I 的开课。

前方的路注定不好走，但是要慢慢尝试和坚持。

4. 算法的空间复杂度和时间复杂度的关系

论坛

活动

招聘

专题

打开CSDN APP
Copyright © 1999-2020, CSDN.NET, All Rights Reserved

搜索博文/帖子/用户
登录

zolalad
关注
算法的时间复杂度和空间复杂度-总结 原创
2013-09-20 16:01:26
308点赞

zolalad

码龄9年

关注
算法的时间复杂度和空间复杂度-总结
通常，对于一个给定的算法，我们要做 两项分析。第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法是正确的基础上，第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。因此，作为程序员，掌握基本的算法时间复杂度分析方法是很有必要的。
算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。

一、事后统计的方法

这种方法可行，但不是一个好的方法。该方法有两个缺陷：一是要想对设计的算法的运行性能进行评测，必须先依据算法编制相应的程序并实际运行；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优势。

二、事前分析估算的方法

因事后统计方法更多的依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此人们常常采用事前分析估算的方法。

在编写程序前，依据统计方法对算法进行估算。一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

(1). 算法采用的策略、方法；(2). 编译产生的代码质量；(3). 问题的输入规模；(4). 机器执行指令的速度。

一个算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执行的次数作为算法的时间量度。

1、时间复杂度
（1）时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
（2）时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

另外，上面公式中用到的 Landau符号其实是由德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的着作《解析数论》首先引入，由另一位德国数论学家艾德蒙·朗道（Edmund Landau）推广。Landau符号的作用在于用简单的函数来描述复杂函数行为，给出一个上或下（确）界。在计算算法复杂度时一般只用到大O符号，Landau符号体系中的小o符号、Θ符号等等比较不常用。这里的O，最初是用大写希腊字母，但现在都用大写英语字母O；小o符号也是用小写英语字母o，Θ符号则维持大写希腊字母Θ。
T (n) = Ο(f (n)) 表示存在一个常数C，使得在当n趋于正无穷时总有 T (n) ≤ C * f(n)。简单来说，就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。也就是说当n趋于正无穷时T (n)的上界是C * f(n)。其虽然对f(n)没有规定，但是一般都是取尽可能简单的函数。例如，O(2n2+n +1) = O (3n2+n+3) = O (7n2 + n) = O ( n2 ) ，一般都只用O(n2)表示就可以了。注意到大O符号里隐藏着一个常数C，所以f(n)里一般不加系数。如果把T(n)当做一棵树，那么O(f(n))所表达的就是树干，只关心其中的主干，其他的细枝末节全都抛弃不管。
在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。 按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

从图中可见，我们应该尽可能选用多项式阶O(nk)的算法，而不希望用指数阶的算法。

常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

一般情况下，对一个问题（或一类算法）只需选择一种基本操作来讨论算法的时间复杂度即可，有时也需要同时考虑几种基本操作，甚至可以对不同的操作赋予不同的权值，以反映执行不同操作所需的相对时间，这种做法便于综合比较解决同一问题的两种完全不同的算法。

（3）求解算法的时间复杂度的具体步骤是：

⑴ 找出算法中的基本语句；

算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

⑵ 计算基本语句的执行次数的数量级；

只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

⑶ 用大Ο记号表示算法的时间性能。

将基本语句执行次数的数量级放入大Ο记号中。

如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：

for (i=1; i<=n; i++)
x++;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
x++;
第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。

Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为P（Polynomial,多项式）类问题，而把后者（即指数时间复杂度的算法）称为NP（Non-Deterministic Polynomial, 非确定多项式）问题。

一般来说多项式级的复杂度是可以接受的，很多问题都有多项式级的解——也就是说，这样的问题，对于一个规模是n的输入，在n^k的时间内得到结果，称为P问题。有些问题要复杂些，没有多项式时间的解，但是可以在多项式时间里验证某个猜测是不是正确。比如问4294967297是不是质数？如果要直接入手的话，那么要把小于4294967297的平方根的所有素数都拿出来，看看能不能整除。还好欧拉告诉我们，这个数等于641和6700417的乘积，不是素数，很好验证的，顺便麻烦转告费马他的猜想不成立。大数分解、Hamilton回路之类的问题，都是可以多项式时间内验证一个“解”是否正确，这类问题叫做NP问题。

（4）在计算算法时间复杂度时有以下几个简单的程序分析法则:

(1).对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间

(2).对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"

求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))

特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))

(3).对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间

(4).对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"

乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n))

(5).对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度

另外还有以下2个运算法则:(1) 若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一个正常数

（5）下面分别对几个常见的时间复杂度进行示例说明：

(1)、O(1)

Temp=i; i=j; j=temp;

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
(2)、O(n2)

2.1. 交换i和j的内容

sum=0； （一次）
for(i=1;i<=n;i++) （n+1次）
for(j=1;j<=n;j++) （n2次）
sum++； （n2次）
解：因为Θ(2n2+n+1)=n2（Θ即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以T(n)= =O(n2)；

2.2.

for (i=1;i<n;i++)
{
y=y+1; ①
for (j=0;j<=(2*n);j++)
x++; ②
}
解： 语句1的频度是n-1
语句2的频度是(n-1)*(2n+1)=2n2-n-1
f(n)=2n2-n-1+(n-1)=2n2-2；

又Θ(2n2-2)=n2
该程序的时间复杂度T(n)=O(n2).

一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

(3)、O(n)

a=0;
b=1; ①
for (i=1;i<=n;i++) ②
{
s=a+b;③
b=a;④
a=s;⑤
}
解： 语句1的频度：2,
语句2的频度： n,
语句3的频度： n-1,
语句4的频度：n-1,
语句5的频度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).
(4)、O(log2n)

i=1; ①
while (i<=n)
i=i*2; ②
解： 语句1的频度是1,
设语句2的频度是f(n), 则：2^f(n)<=n;f(n)<=log2n
取最大值f(n)=log2n,
T(n)=O(log2n )

(5)、O(n3)

for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
}
}
解：当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n3).

（5）常用的算法的时间复杂度和空间复杂度

一个经验规则：其中c是一个常量，如果一个算法的复杂度为c 、 log2n 、n 、 n*log2n ,那么这个算法时间效率比较高 ，如果是2n ,3n ,n!，那么稍微大一些的n就会令这个算法不能动了，居于中间的几个则差强人意。

算法时间复杂度分析是一个很重要的问题，任何一个程序员都应该熟练掌握其概念和基本方法，而且要善于从数学层面上探寻其本质，才能准确理解其内涵。

2、算法的空间复杂度

类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地\"进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。

如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，