有书共读07笔记【算法图解】1-2章
第一章
算法简介
- 算法是什么，算法就是为了解决问题的思路吧。由此也就产生了很多解决问题的模型。问题无处不在，解决问题就需要效率，就好比生活中有的人办事就是效率高，但有的人办事就很差劲。书中一个例子讲的是二分查找算法，算法将需要执行的步骤从40亿个减少到了32个，这就是算法，所以我们需要学习解决问题的这种“思路”，提高完成问题的效率。
- 书中谈到学习算法需要一些基本的代数知识。具体地说，给定函数f(x) = x × 2， f(5)的值是多 少呢？如果你的答案为10，那就够了。
二分查找
好比说我们取作业本，然后本子上面都有自己的号码，都按顺序排好了，然后你的号码是51个人中的34号，你要拿走你的本子，你会怎么拿，我相信你肯定不会从头顺着一本一本的找，直接翻到中上部位置，自己的号码肯定就在这附近。书中的例子是猜数字游戏，以最少次数猜到这个数字，我这里贴一下我写的java代码：
public static void main(String[] args) {
Scanner scan = new Scanner(new BufferedInputStream(System.in));
int[] number = new int[100];
for (int i = 1; i <= 100; i++) {//从1-100个数字里面猜
number[i-1] = i;
}
int set = scan.nextInt();//设置一个数字让计算机猜
int l = 0;//左边
int r = number.length-1;//右边
while (l <= r) {
int center = (l + r) / 2;
int guess = number[center];
if (guess == set) {
System.out.println("猜中了，哈哈，答案就是" + set);
break;
} else if (guess < set) {
System.out.println("你猜小了,不是"+guess);
l = center + 1;
} else {
System.out.println("你猜大了,不是"+guess);
r = center - 1;
}
}
} 小结
- 二分查找的速度比简单查找快得多。
- O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。
- 算法运行时间并不以秒为单位。
- 算法运行时间是从其增速的角度度量的。
- 算法运行时间用大O表示法表示。
第二章
选择排序
- 我还是想说上面那个作业本的例子，好比说你就是学习***哈，然后同学们的本子都是学号乱序地交给了你，可是你要顺序的排好了交给老师，怎么办？怎么办？你会怎么办？这里呢，先说一个最笨的方法，也就是这个选择排序算法，它会怎么排呢？每次会找到那个最小号的学号，然后将它拿出来，放在一边，好比说我第一次应该要找1号，找到了就放在另一堆，第二次要找2号，找到了也放另一堆，，，，这一堆放着放着不就是顺序了的嘛。
- 分析下时间复杂度
随着排序的进行，每次需要检查的元素数在逐渐减少，最后一次需要检查的元素都只有一
个。既然如此，运行时间怎么还是O(n2)呢？这个问题问得好，这与大O表示法中的常数相关。
第4章将详细解释，这里只简单地说一说。
你说得没错，并非每次都需要检查n个元素。第一次需要检查n个元素，但随后检查的元素
数依次为n 1, n – 2, …, 2和1。平均每次检查的元素数为1/2 × n， 因此运行时间为O(n × 1/2 × n)。
但大O表示法省略诸如1/2这样的常数（有关这方面的完整讨论，请参阅第4章），因此简单地写
作O(n × n)或O(n2)。
最后我得贴下我的代码，这里用java实现（虽然我python3也会用，但java用的比较熟，）：
public static void main(String[] args) {
int[] number = new int[10];
Random ran = new Random();
for(int i = 0;i<10;i++){
number[i] = ran.nextInt(10)+1;//ran.nextInt(10)-->[0,10)
}
System.out.println(Arrays.toString(number));//排序前
for(int i = 0;i<number.length;i++){
for(int j = i;j<number.length;j++){
if(number[i] >= number[j]){//找到最小的让它顺序排到数组前面
int f = number[i];
number[i] = number[j];
number[j] = f;
}
}
}
System.out.println(Arrays.toString(number));//排序后
} 小结
- 计算机内存犹如一大堆抽屉。
- 需要存储多个元素时，可使用数组或链表。
- 数组的元素都在一起。
- 链表的元素是分开的，其中每个元素都存储了下一个元素的地址。
- 数组的读取速度很快。
- 链表的插入和删除速度很快。
- 在同一个数组中，所有元素的类型都必须相同（都为int、 double等）
