CS50X前4讲的小笔记

仅记录我复习后觉得能学习到的知识。(为了1024)

不包括C语言的知识点

1.

O(n)描述的是一个算法的上限（在最坏情况下需要执行多少步）

Ω(n)描述的是一个算法的下限（在最完美情况下需要执行多少步）

θ(n)描述的是一个算法上下限相等（不管最坏或是最完美情况下，都要执行相同次数）

其中，括号内可以为其他数学公式，比如logn，n²，1之类的，且忽略常数，只注重表达公式中数量级。 如最坏情况下 一个算法需要执行n/2次和另一个算法另一个算法需要执行n次，在描述时都会变成O（n）

例如选择排序就是θ(n²)的  即使在数组初始就已经排好的情况下，任然需要一次又一次的去检查，最终才能确定排序好了，（只不过缺少了找出最小的那个 跟前面未排序好的部分交换的步骤，但不影响数量级），合并排序是θ(nlogn)

2.选择算法时，更多是做衡量，如直接用线性算法来查找某数据，还是先排序，再用二分法来查找数据，跟多的是取决于实际情况，如果数据是无序的，且添加他的频率比查找他的频率高，也许这种时候用线性查找会比用二分法高效一点，（因为不需要排序），如果数据是无序的，但添加他的频率远少于查找他的频率（查找多，添加少），那么在查找之前对数据进行排序，并保存，以便用于之后可能会多次出现的二分查找，会比使用线性查找法会高效。

同样，这样的衡量不止是出现在关心算法执行次数时，也有可能会出现在关心算法运行时所占用的资源(比如内存，储存空间）等其他情况。多数情况下选择算法会发生在衡量使用空间与运行时间时，选择一个两者都能兼顾的方案，以达到某种平衡。

3..在编写程序时，除了编辑器，编译器和调试器可以帮你发现错误，还有一类工具，专门用于内存调试，检测内存泄露或检测线程错误的工具，例如valgrind

例如

#include <stdio.h>

#include <stdlib.h>

void main(void){

int *x = malloc(3*sizeof(int));

x[1] = 72;

x[2] = 72;

x[3] = 72;

}

会导致两个问题：

1.数组索引超过边界（有概率导致段错误Segmentation fault）

2.内存泄露（因为用了malloc但没有用free释放）

编辑器和编译器会提示第一个问题，但有可能会遗漏第二个问题

所以在编写程序时，有时必须对内存管理进行检查，是否有泄露是否可能越界啥的

4.垃圾值：如在C中，如果你申请了一个数组 但没有对其进行初始化，然后便访问他，会看到之前被系统遗漏的数据（也就是说 系统给出内存空间时候，并不会自动帮你做全部归0的初始化），这意味着漏洞，hack可以通过某种方式看到系统中的内存(万一看到某人的密码之类的)，从而增加软件被攻破之类的威胁。

5.堆栈溢出

如图所示，在内存中，不同区域用作不同目的的储存

一个程序的储存被抽象为如图4个部分，第一个部分程序作为编译完的机器码的储存部分，储存了程序对计算机要做的指令（被翻译成机器码） 即代码区

第二个部分储存的是全局变量的数据 即全局数据区

第三部分在上面heap为堆 即堆区 用于储存如C中程序员通过malloc的方式自己申请的内存区域(也需要程序员自己手动释放)。 初始起点较低，随着堆越来越多 地址越来越高（即向上）

第四部分在下面stack为栈 即栈区，用于储存通过操作系统分配的如变量和函数返回地址等数据，由操作系统（编译器）自己管理分配和释放空间，初始起点较高，随着栈越来越低，地址越来越低（即向下）。

这也就能解释在C中为什么通过malloc分配的地址会很低 而局部变量的地址会很高。

当第三部分和第四部分都在申请空间 直到空间不够双方相撞（这是个比喻啦），便是双方互相溢出，即堆栈溢出。