时间复杂度的计算

算法

定义

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

• 一个有限指令集
• 接受一些输入
• 产生输出
• 一定在有限步骤后终止
• 每一条指令必须：
  有充分明确的目标，不可以有歧义
  计算机能处理的范围之内
  描述应不依赖于任何一种计算机语言以及具体的实现手段

算法设计的要求

正确性、可读性、健壮性、时间效率高和存储量低

算法效率的度量方法

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

例：求第n个斐波那契数列

**事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算** 程序在计算机上运行时所消耗的时间取决于以下几个因素：

1. 算法采用的策略、方法==>算法好坏的根本
2. 编译产生的代码质量==>由IDE、软件支持
3. 问题的输入规模
4. 机器执行指令的速度==>看计算机硬件的性能

时间复杂度

什么是时间复杂度

• T(n)=O(f(n))

• T(n)表示代码执行时间;
• n表示数据规模的大小;
• f(n)表示每行代码执行的次数总和.
• 因为这是一个公式,所有用f(n)来表示.公式中的O,表示代码的执行时间T(n)与f(n)成正比.
• 大O时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度

函数的渐近增长

算法A 要做2n+3次操作 算法B要做3n+1次操作

次数	算法A（2n+3）	算法A‘（2n）	算法B（3n+1）	算法B’（3n）
n=1	5	2	4	3
n=2	7	4	7	6
n=3	9	6	10	9
n=10	23	20	31	30
n=100	203	200	301	300

输入规模n在没有限制的情况下，只要超过一个数值N，这个函数就总是大于另一个函数，我们称函数是渐近增长的
函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N,f(n)总是比g(n)大，那么，我们说f(n)的增长渐近快于g(n)。

---

一秒之内能解决问题的数据规模

	数据规模	时间复杂度
1	10	n！
2	20~30	2^n
3	50	n^4
4	100	n^3
5	1000	n^2
6	10^6	nlogn
7	10^7	n
8	10^9	sqrt(n)
9	10^10	logn
10	无穷大	1

阿里面试题

假设给出一个算法的时间复杂度递推关系式：T(n）=T(n-1)+n，T(0)=1；（n为整数）求该算法的时间复杂度