算法复杂度计算⽅法
时间复杂度：⼀段代码或函数会根据N的不同情况运⾏多少次，并只看最⾼复杂度的运算。常见复杂度排序：
cantans complexity 常数级复杂度O(1) < logarithmic complexity 对数复杂度O( log(n) ) < linear complexity线性时间复杂度O(n) < O( nlog(n) ) < 平⽅O(n^2) < ⽴⽅O(n^3) < 指数O (2^n) < 阶乘O(n!)
空间复杂度：通常⽤数组长度和递归深度或取两者最⼤值来定义
关于主定理：
百度百科 ：在算法分析中，⽀配理论（英语：master theorem）提供了⽤渐近符号（⼤O符号）表⽰许多由分治法得到的递推关系式的⽅法。这种⽅法最初由Jon Bentlery，Dorothea Haken和James B. Saxe在1980年提出，在那⾥被描述为解决这种递推的“天下⽆敌法”(master method)。此⽅法经由经典算法教科书Cormen，Leiserson，Rivest和Stein的《算法导论》 (introduction to algorithm)推⼴⽽为⼈熟知。
作⽤ ：可以⽤来解决所有递归函数如何计算其时间复杂度的问题，即任何⼀个分治或递归的函数都可以通过主定理算出它的时间复杂度
⾯试和平时⼯程中常⽤的四种递归情形及时间复杂度计算公式：
⼆分查： 递归公式：T(n) = T(n/2) + O(1) 时间复杂度：O( log(n) )
⼆叉树遍历： 递归公式：T(n) = 2T(n/2) + O(1) 时间复杂度：O(n )
⼆维矩阵⼆分查：递归公式T(n) = 2T(n/2) + O(log(n)) 时间复杂度：O(n )
归并排序： 递归公式：T(n) = 2T(n/2) + O(n) 时间复杂度：O(n log(n) )
还有图的遍历，DFS和BFS搜索遍历也很重要，时间复杂度都是O(n)，因为每个节点都要访问⼀次且仅⼀次二叉树公式

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。