数据结构与算法-复杂度(时间和空间)

为了引入数据结构与算法的重要性,首先举个例子:

你要在一个在线系统中实时处理数据,假设这个系统平均每分钟会新增 300M 的数据量,如果你的代码不能在 1 分钟内完成对这 300M 数据的处理,那么这个系统就会发生时间爆炸和空间爆炸。表现就是,电脑执行越来越慢,直到死机。因此,我们需要讲究合理的计算方法,去通过尽可能低复杂程度的代码完成计算任务。

时间复杂度的经验性总结:

  • 一个顺序结构的代码,时间复杂度是 O(1)。
  • 二分查找,或者更通用地说是采用分而治之的二分策略,时间复杂度都是 O(logn)。
  • 一个简单的 for 循环,时间复杂度是 O(n)。
  • 两个顺序执行的 for 循环,时间复杂度是 O(n)+O(n)=O(2n),其实也是 O(n)。
  • 两个嵌套的 for 循环,时间复杂度是 O(n²)。

为了更好理解,我们来看一些数据。

假设某个计算任务需要处理 10万 条数据。你编写的代码:

  • 如果是 O(n²) 的时间复杂度,那么计算的次数就大概是 100 亿次左右。
  • 如果是 O(n),那么计算的次数就是 10万 次左右。
  • 如果这个工程师再厉害一些,能在 O(log n) 的复杂度下完成任务,那么计算的次数就是 17 次左右(log 100000 = 16.61,计算机通常是二分法,这里的对数可以以 2 为底去估计)。

复杂度通常包括时间复杂度和空间复杂度。在具体计算复杂度时需要注意以下几点。

  • 复杂度与具体的常系数无关,O(n) 和 O(2n) 表示的是同样的复杂度。
  • 复杂度相加的时候,选择高者作为结果,也就是说 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度。
  • O(1) 也是表示一个特殊复杂度,即任务与算例个数 n 无关。

程序员未雨

Do one thing at a time, and do well.

暂无评论

发表评论

您的电子邮件地址不会被公开,必填项已用*标注。

相关推荐

暂无相关文章!

微信扫一扫

微信扫一扫

微信扫一扫,分享到朋友圈

数据结构与算法-复杂度(时间和空间)