• 正在学习的算法课程：极客时间的王争老师的《数据结构与算法之美》
• 传送门： https://time.geekbang.org/column/126
• 目前学到第三讲，很良心，共56讲，推荐想学数据结构的同学
• 以下为学习笔记，最近忙着写论文，今天差不多完成了初稿了，争取日更
• 2019/09/22

一、时间复杂度影响因素

1. 测试环境
2. 数据级规模大小

二、时间复杂度概念 - 大O

带着问题学习

---

Q1. 以下代码的执行时间为？

 int cal(int n) {int sum = 0;int i = 1;for (; i <= n; ++i) {sum = sum + i;}return sum;}

A: 总共：1 + 1 + n + n = 2n +2

---

Q2. 以下代码的执行时间为？

 int cal(int n) {int sum = 0;int i = 1;int j = 1;for (; i <= n; ++i) {j = 1;for (; j <= n; ++j) {sum = sum + i * j;}}}

A：$1+1+1+n+n+n^2+n^2=2n^2+2n+2$
结论： ** 所有代码执行时间T(n)与每行代码的执行次数成正比 **

---

1. 概念

$$T(n)=O(f(n))$$
大O： 其中，n是数据规模的大小。代码的执行时间T(n)和每一行代码的执行时间f(n)成正比，表示代码执行时间随着数据集数据规模增长的变化趋势，全名叫做时间渐进复杂度，简称时间复杂度（ 只保留最高阶）

2. 时间复杂度技巧分析

• 只关注循环次数做的一段代码

 int cal(int n) {int sum = 0;int i = 1;for (; i <= n; ++i) {sum = sum + i;}return sum;}

时间复杂度：O(n)

• 加法法则，只保留最大量级

int cal(int n) {int sum_1 = 0;int p = 1;for (; p < 100; ++p) {sum_1 = sum_1 + p;}int sum_2 = 0;int q = 1;for (; q < n; ++q) {sum_2 = sum_2 + q;}int sum_3 = 0;int i = 1;int j = 1;for (; i <= n; ++i) {j = 1; for (; j <= n; ++j) {sum_3 = sum_3 + i * j;}}return sum_1 + sum_2 + sum_3;}

时间复杂度：$O(1+n+n^2)=O(n^2)$

• 乘法法则：嵌套代码的复杂度为嵌套内外代码复杂度的乘积

int cal(int n) {int ret = 0; int i = 1;for (; i < n; ++i) {ret = ret + f(i);} } int f(int n) {int sum = 0;int i = 1;for (; i < n; ++i) {sum = sum + i;} return sum;}

时间复杂度：$O(n^2)$

3. 几种常见时间复杂度

• O(1)
  代码运算为常量级的时间复杂度，与数据规模n无关，均为O(1)

 int i = 8;int j = 6;int sum = i + j;

• O(logn)、O(nlogn)
  通过代码来解析O(logn)，看如下代码：

 i=1;while (i <= n) {i = i * 2;}

上述代码的时间复杂度即为第三行代码计算所需的时间，第三行代码计算时间所需如下：

转换成了求x的值，$x=lo{g}_2(n)$ ，那么$O(nlogn)$即为在复杂度$x=log(n)$外面嵌套一层时间复杂度为n的代码

Ps: 不管对数底为几，统记为$log(n)$，可以这么记的原因是对数的相互转换公式

• O(m+n)、O(m*n)
  看代码解析，代码如下：

int cal(int m, int n) {int sum_1 = 0;int i = 1;for (; i < m; ++i) {sum_1 = sum_1 + i;}int sum_2 = 0;int j = 1;for (; j < n; ++j) {sum_2 = sum_2 + j;}return sum_1 + sum_2;
}

m和n是两个数据集的规模大小，m和n的谁大谁小未知，因此时间复杂度为O(m+n)

三、空间复杂度分析

1. 概念

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系;
空间复杂度的全称是渐进空间复杂度，表示算法的存储空间和数据规模之间的增长关系

2. 代码分析 & 常用的空间复杂度

先上代码：

void print(int n) {int i = 0;int[] a = new int[n];for (i; i <n; ++i) {a[i] = i * i;}for (i = n-1; i >= 0; --i) {print out a[i]}
}

看第三行代码，申请了一个大小为n的int型数据，之后的代码都是在该数据中操作，并没有改变大小，因此上述代码的空间复杂度为O(n)

---

• 平时常用的空间复杂度：O(1)、O(n)、$O(n^2)$，很少用到对数的复杂度

四、小结

1. 从低阶到高阶的复杂度：O(1)、O(logn)、O(n)、O(nlogn)、$O(n^2)$
   
2. 课后代码实现题（2019年地平线浙大秋招现场编程题）

给定一个数组，一开始顺序从小变大，接着到达某个值之后，顺序从大变小，请设计一个复杂度为O(logn)的算法，找到这个最大值

update:2019/09/23

# coding=utf-8
'''
@ Summary: 给定一个数组，一开始顺序从小变大，接着到达某个值之后，顺序从大变小，请设计一个复杂度为O(logn)的算法，找到这个最大值思路： 判断中点，舍掉左边或者右边，递归
@ Update:  @ file:    O(nlogn).py
@ version: 1.0.0@ Author:  Lebhoryi@gmail.com
@ Date:    19-9-23 下午6:05
'''def local_maximum(l):if not l:return Noneif len(l) == 1:return l[0]else:mid = int(len(l)/2)l = l[:mid+1] if l[mid] >= l[mid+1] else l[mid+1:]return local_maximum(l)if __name__ == "__main__":# import sys# _list = list(map(int, sys.stdin.readline().strip().split()))_list = [1, 2, 3, 4, 3, 2]result = local_maximum(_list)print(result)