复杂度分析

什么是复杂度？

算法的复杂度是粗略衡量一个算法执行效率的方法，分为时间复杂度和空间复杂度。

时间复杂度：估算程序指令的执行次数（时间）

空间复杂度：估算所需占用的存储空间

大O表示法

一般用大O表示法来描述复杂度，他表示的是数据规模n对应的复杂度

所有代码的执行时间 T(n) 与每行代码的执行次数 f(n) 成正比。

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

T(n)表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度，简称时间复杂度。

用大O复杂度表示法，通常我们会忽略常数、系数、低阶

常见的复杂度量级：O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)

举个栗子：

假如每一行代码执行时间都是一样的unit_time，这段代码执行时间为(2n+2)*unit_time，所以时间复杂度为O(n)。

多个数据规模的例子：

这个例子里复杂度依赖两个数据规模，所以时间复杂度为O(m+n)

空间复杂度：

表示算法的存储空间与数据规模之间的增长关系。

常见的空间复杂度就是 O(1)、O(n)、O(n2 )

申请了一个大小为 n 的 int 类型数组，同时申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略，所以整段代码的空间复杂度就是 O(n)。

算法的优化方向：

1.用尽量少的存储空间

2.用尽量少的执行步骤（执行时间）

根据情况，可以用空间换时间，用时间换空间

leetcode斐波那契数列：

https://leetcode-cn.com/problems/fibonacci-number/