c#数据结构与算法（1）预备知识

该文档主要是本人的学习笔记，用于备忘，若有侵权，可随时联系删除！
参考学习网址：

• https://www.dotcpp.com/course/94
• https://www.cnblogs.com/manuosex/tag/C%23/default.html?page=1
• https://blog.csdn.net/qq_41603955/article/details/123470533

一、数学基础
等比数列，等差数列等很基础，公式一搜遍地都是，不再赘述

二、数据结构发展历史
1、无结构阶段：程序处理的是纯粹的数值，数据关系主要为数学公式或数学模型
2、结构化阶段：用于非数值处理领域，数据表示成为数据设计的重要问题
3、面向对象：减少重复设计的部分，大量的封装类出现，减少了程序设计者的负担

三、算法
计算1-100的和（循环加一遍or用等差数列求和？），方法不同效率不同

1、算法特性
1）输入输出：算法具有零个或者多个输入，具有至少一个的输出。
2）确定性：相同的输入智能得到相同的输出
3）有穷性：在有限的步骤结束
4）可行性

2、设计要求
1）正确性：满足余弦指定的功能与性能的需求
A、无语法错误 B、对于几组输入能够得到满足需求的结果
C、对于非法输入抛出异常 D、严苛数据依旧能产生满足需求的结果
2）健壮性：输入数据不合法，能作出相关处理
3）可读性
4）耗时低、占用空间少

四、数据结构基础
1、基本概念和术语
1）数据：计算机识别、存储和加工处理的信息符号（整形、浮点型、声音、视频、图像）
2）数据元素：基本单位，一个数据元素由若干个数据项组成
3）数据项：描述数据的最小单位
4）数据对象是性质相同的一类数据元素的集合，是数据的一个子集
5）数据结构：数据和关系的集合

五、四大逻辑结构
1、集合结构：除同属一个集合外，并无其他关系

2、线性结构：数据元素之间存在一对一关系

3、树形结构：一对多

4、图形结构：多对多

六、数据类型
1）数据类型：取值范围和对数进行操作的总和
2）抽象数据类型：数学模型及模型上的操作，与操作分离，从而实现封装

七、复杂度
1、时空复杂度定义
1）时间复杂度：运行所需时间
时间频度T(n)=O(f(n))，O(f(n))为时间复杂度
2）空间复杂度：所需内存大小
固定部分：代码空间、数据空间等（静态）
可变空间：动态分配空间（递归栈所需空间），与算法有关
2、度量时间复杂度
1）事后统计法：统计比较算法运行时间（测试较为困难）
2）事先估计法：O表示最坏情况、Ω表示最好情况，θ表示平均情况(一般用O)

八、时间复杂度的度量方法
O(n)函数中间的值为程序执行的步骤次数
主要观察程序中的循环结构，每一个循环结构代表执行循环中的指令n次
1、O(1)  /  O(C)  C代表常数
2、O(n)
3、O(n^2)
4、O(logn)

int i=1,n=10000;    //执行一次
    while(i<=n){    //执行logn次
        i*=2;
    }
    return 0;       //执行一次

while(x >= (y+1)*(y+1))
{
   y=y+1; ①
}

大小关系：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)