FDS（零）：预备

学习FDS之前在网上查到的一些目前觉得应该会比较有用的资料与网站，以及需要的预备知识

资料网站

可视化网站

数据结构可视化 — Data Structure Visualization (usfca.edu)

菜鸟教程

数据结构与算法 | 菜鸟教程 (runoob.com)

学习总纲

数据结构与算法分析

（本系列文章大部分参考于该网站）

发现一个更美观的网站：Hello 算法 (hello-algo.com)

算法学习网站

PikaPika - LeetCode

预备知识

理解复杂度概念

Predict the growth in run time as the N change

1. 时间复杂度

时间复杂度表示一个程序运行所需要的时间，其具体需要在机器环境中才能得到详细的值，但我们一般不需要得到详细的值，只是需要比较快慢的区别即可，为此，我们需要引入时间频度（语句频度）的概念

时间频度中，n 称为问题的规模，当 n 不断变化时，时间频度 T(n) 也会不断变化，一般情况下，算法中的基本操作重复次数时问题规模的某个函数，一般用 T(n) 表示，若有某个辅助函数 f(n) 使得当 n 趋向于无穷大时，T(n)/f(n) 的极限值为不等于零的常数，则称 f(n) 是 T(n) 的同数量级函数。记作T(n)=Ｏ(f(n)) ,称 Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

2. 空间复杂度

一个程序的空间复杂度是指运行完一个程序所需内存的大小，其包括两个部分。

a) 固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。

b) 可变空间。这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。

对算法进行预估：

函数符号：

〇表示最坏情况（上界），Ω表示最好情况(下界)，θ表示平均情况（等价），我们常用的分析，使用O进行表示即可。对于一个算法的时间复杂度而言，n表示其执行问题的规模，O(n)表示执行该问题需要的时间量级，

程序串行，时间复杂度取最大的那个，程序嵌套，实践复杂度相乘

logN grow very slowly

如O(n)表示线性级别，

O(n^2^)表示平方级别，

其中 f(n) 主要的判断方式为算法中循环结构的执行次数。

预估方法：

观察程序中循环的次数

例如：O（1）/ O（C），C代表常数

#include<stdio.h>
int main(){
    printf("Hello World");  //执行一次
    return 0;       //执行一次
}

例如：O（logN）

#include<stdio.h>
int main(){
    int i=1,n=10000;    //执行一次
    while(i<=n){    //执行logn次
        i*=2;
    }
    return 0;       //执行一次
}

又例如：O（N*logN）

#include<stdio.h>
int main(){
    int n=10000,ans=0;  //执行一次
    for(int i=0;i<n;i++){   //执行n次,其实判断的语句执行了n+1次
        int j=0;        //执行1次
        while(j<=n){    //执行log(n)次
            j*=2;
        }
    }
    return 0;       //执行一次
}

可以非常直观地得出：

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2^) < O(n^3^) < O(2^n^)

example

matrix addition