1.1 引言
概念:算法是一组完成任务的指令。
学习过程:描述算法+提供实例+运行时间(大O表示法)+探索其他功能
1.2 二分查找
(1)二分查找是一种算法,其输入是一个有序的元素列表(必须有序的原因稍后解释)。如果要查找的元素包含在列表中,二分查找返回其位置;否则返回null。
(2)
(3)运行时间
1.3 大O表示法:
(1)大O表示法指出了算法有多快:
例如,假设列表包含n个元素。简单查找需要检查每个元素,因此需要执行n次操作。使用大O表示法,这个运行时间为O(n)。单位秒呢?没有——大O表示法指的并非以秒为单位的速度。大O表示法
让你能够比较操作数,它指出了算法运行时间的增速。
(2)大O表示法指出了最坏情况下的运行时间
下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。
O(log n),也叫对数时间,这样的算法包括二分查找
O(n),也叫线性时间,这样的算法包括简单查找。
O(n * log n),这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
O(n2),这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
O(n!),这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。