面试算法

面试算法

复杂度

时间复杂度（面试必考）

定义：时间复杂度使用标记O(大写英文字母o)表示，只包含上述多项式中的最高次项，且忽略最高次项的系数

只包含多项式的最高次项

不包含多项式最高次项的系数

程序执行了多少句语句

常见复杂度

O(1)

位运算，一般不考

O(logn)(以2为底)

二分法，倍增法，快速幂算法，辗转相除法

O(n)

枚举法，双指针算法，单调栈算法，KMP算法，Rabin Karp算法，Manacher's Algorithm

O(nlogn)

快速排序，堆排序，归并排序

O(n^2)

枚举法，动态规划法，Dijkstra

O(n^3)

枚举法，动态规划法，Floyd

O(2^n)

与组合有关的搜索问题

O(n!)

与排列有关的搜索问题

T函数推导法

时间复杂度的推导方法

T(n)=T(n/2)+O(1)

T(n) 代表的就是：求处理问题规模为n的数据的时间复杂度是多少

O 代表的是时间复杂度

O 在这里的意思是数量级约等于

在 O 的世界里，我们只考虑最高项是什么，不考虑系数和常数项

空间复杂度（面试基本不考）

空间类型

代码本身占用空间，不考虑

输入，输出占用空间，不考虑

临时变量占用空间，考虑

变量数量

数组

递归的栈空间

与递归的深度成正比

面试

不能使用多余的空间

要求你的空间复杂度只能是O(1)O(1)

只能开几个辅助变量，而不能开大数组

分析一下你的算法空间复杂度

寻找空间复杂度更优的解法

算法占用的时间和空间会是两个互相平衡的元素，有的时候我们牺牲空间来换取时间，有的时候我们牺牲时间来换取空间。

快速排序： 最优：O(logn)O(logn)，最差:O(n)O(n)

二分查找： O(1)O(1)

最短路(Dijkstra)算法： O(V)O(V)(VV表示点集大小)

分支主题

公众号《湾区人工智能》发布