面试算法
2018-09-25 18:33:32 31 举报AI智能生成
面试常见算法
作者其他创作
大纲/内容
复杂度
时间复杂度（面试必考）
定义：时间复杂度使用标记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 代表的是 Time Complexity, nn 代表的是问题规模
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表示点集大小)
分支主题
分支主题
分支主题
分支主题
公众号《湾区人工智能》发布
0 条评论
下一页
