数据结构与算法基础-开篇

  • A+
所属分类:算法基础
摘要这是关于数据结构与算法的第一篇内容, 算是这个系列的一个开篇. 简单介绍一下时间复杂度的内容, 同时说明一下我是如何来进行练习的.

简介

从这一篇开始, 会记录数据结构与算法的相关内容, 每一篇会介绍相关的内容和leetcode上的例题分析. 也是第一次开始写这个, 就慢慢往里面进行补充.

这第一篇, 介绍一下时间复杂度, 包括递归问题的时间复杂度的计算. 最后包含一些常见递归算法的时间复杂度. 最后写一下自己练习的方式, 要每天坚持练习.

 

时间复杂度

关于时间复杂度, 我们通常使用Big-O来表示程序最坏情况下的时间复杂度. 有下面几种情况.

数据结构与算法基础-开篇

下面对每一种进行一些介绍, 什么情况下会出现.

  • O(1)
  • O(logn): for (i=1, i<n, i=i*2), 后面会给出详细介绍
  • O(n): for循环
  • O(n^2): 双重循环
  • O(2^n): for中, 包含i<2^n, (i=1, i<2^n, i++)
  • O(n!): for中, 包含i<n!, (i=1, i<n!, i++)

关于O(logn)的时间复杂度, 我们在这里多介绍一些, 即为什么(i=1, i<n, i=i*2)的复杂度是logn.

数据结构与算法基础-开篇

 

关于递归问题的时间复杂度

关于递归问题的时间复杂度需要使用Master theorem, 参考链接, Master theorem (analysis of algorithms). 我们这里就看一个简单的例子, 使用fibonacci sequence作为例子.

比如我们要计算f(5), 这时候就需要计算f(5)=f(4)+f(3), 最终的递归树如下所示:

数据结构与算法基础-开篇

从上面递归树可以看出, 此时需要计算15次. 其实这里大概的次数是2^n, 也就是这里如果使用递归计算, 计算第N个数字, 时间复杂度是O(2^n).

参考资料: Time and Space Complexity of Recursive Algorithms

 

常见递归算法时间复杂度

  • Binary search(二分查找): O(logn)
  • Binary Tree Traversal(二叉树遍历): O(n)
  • Merge Sort(归并排序): O(n*logn)
  • Quick Sort(快排): O(n*logn)
数据结构与算法基础-开篇

 

练习方式

这个系列的内容都会基于leetcode上的习题, 之后每次记录内容的时候自己也会去leetcode上做题. 在做题的时候, 需要注意下面的点.

  • 读题, 注意数据的范围
  • 把所有可能的解法都想一下, 综合时间复杂度使用一个最佳的解法
  • 做完题目之后, 查看leetcode上的反馈, 查看discussion

 

  • 微信公众号
  • 关注微信公众号
  • weinxin
  • QQ群
  • 我们的QQ群号
  • weinxin
王 茂南

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: