算法图解笔记 - 算法简介

  • 算法简介
  • 二分查找
  • 数组和链表的操作的运行时间
  • 选择排序
  • 数组和链表总结

算法简介

  • 二分查找到速度比简单查找快得多
  • O(log n)比O(n)快。需要搜索的元素越多,前者比后者就快得越多
  • 算法运行时间并不以秒为单位
  • 算法运行时间是从其增速的角度度量的
  • 算法运行时间用大O表示法表示

二分查找

  • O(log n),也叫对数时间,这样的算法包括二分查找。
  • O(n),也叫线性时间,这样的算法包括简单查找。
  • O(n * log n),这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
  • O(n2),这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
  • O(n!),这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

数组和链表的操作的运行时间 操作数组链表 读取 O(1) O(n) 插入 O(n) O(1) 删除 O(n) O(1) 选择排序 将一组数按照从大到小的顺序排序 算法运行时间O(n*1/2*n),但大O表示法省略诸如1/2这样的常数,因此简单的写作O(n*n) 数组和链表总结

  • 计算机内存犹如一大堆抽屉
  • 需要存储多个元素时,可使用数组或链表
  • 数组的元素都在一起
  • 链表的元素时分开的,其中每个元素都存储了下一个元素的地址
  • 数组的读取速度很快
  • 链表的插入和删除速度很快
  • 在同一个数组中,所有元素的类型都必须(都为int或doubl

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券