算法笔记_面试_0.刷leetcode_基础知识范围

时间复杂度：不考虑系数！

与n的关系

例子

图示:

主定理：

面试题举例：

• 二叉树的前中后序遍历的时间复杂度为多少？
  •  答：都是O(n), 可以根据主定理算出。或者说： 不管那种遍历方式结节都只访问一次，所以线性于节点数，所以时间复杂度是O(n）
  • 同理：图的遍历/DFS(深度优先)/BFS(广度优先)，时间复杂度也都是O(n)
  • 二分查找：时间复杂度：O(logn)
• 空间复杂度： 数组的长度为n,则时间复杂度为O(n)； 对于递归，递归的最大深度即为其时间复杂度。