引言

1. 这是我第一次在CSDN上写博客，难免会有不足之处，希望大家多多包涵。对于一些错误和疏漏，希望能得到各位大佬的批评指正！
2. 由于第一章内容比较少，所以和第二章一起发。我的计划是写一系列这样的学习笔记，大概会有十几期。对于学习期间遇到的一些比较重要的问题或知识点，我会单独的写文章用来梳理和记录。
3. 学习能挡艰难时光，热爱可抵岁月漫长。希望我能和CSDN上的同学们一起学习，一起进步，不负时光，学有所成。

第一章 绪论

知识点梳理

补充：

1. 基本数据类型有：char, int, float, double, viod
2. 构造数据类型有：结构体，共用体，数组，文件

注意事项与易错点

1. 数据项是数据不可分的最小单位。
2. 数据元素是数据结构中建立模型的着眼点。

题型总结

（暂无）

方法与心得

（暂无）

第二章 算法

知识点思维导图

补充：

1. 程序运行时间取决于：
   1）算法采用的策略方法。
   2）编译产生的代码质量。
   3）问题的输入规模。
   4）机器执行指令的速度。
2. 常用时间复杂度所耗时间从小到大依次是：O(n)<O($logn$)<O(n)<O($nlogn$)<O($n^2$)<O($n^3$)<O($2^n$)<O($n!$)<O($n^n$)

注意事项与易错点

（暂无）

题型总结

分析算法的时间复杂度（推导大O阶）

1. 步骤：
   1）计算算法总共执行次数（运行时间）。（算）
   2）用常数1取代运行时间中的所有加法常数。（换）
   2）只保留最高阶项。（删）
   3）如果最高阶项存在且系数不是1，则去除该系数。（查）
2. 注意事项：
   1）单纯的分支结构（不包含在循环中），其时间复杂度是O(1)。
   2）分析算法的时间复杂度，关键就是要分析循环结构的运行情况。
3. 典例：
   1）常数阶

   int sum = 0,n = 100;  //执行1次
   sum = (1 + n) * n / 2; //执行1次
   printf("%d", sum);    //执行1次
   

   计算得运行次数 f(n)=3，时间复杂度为O(1)。
   2）线性阶

   int i;
   for(i = 0; i < n; i++)
   {
   	//时间复杂度为O(1)的程序步骤序列
   }
   

   计算得时间复杂度为O(n)。
   3）对数阶

   int a = 1;
   while (a < n)
   {
   	a = a * 2;
   }
   

   有x个2相乘后大于n，则会退出循环。即$2^x$=n，解得x=$lo{g}_{2}n$，所以其时间复杂度为O(logn)。
   4)平方阶

   int i,j;
   for(i = 0; i < n; i++)
   {
   	for(j = 0; j < n; j++)
   	{
   		//时间复杂度为O(1)的程序步骤序列
   	}
   }
   

   计算得时间复杂度为O($n^2$)。如果外循环变成了m次，则为O(m*n)。
   5）调用方法的时间复杂度

   int i;
   for(i = 0; i < n; i++)
   {
   	function (i) ;
   }
   
   void function (int count)
   {
   	print (count) ;
   }
   

   function()函数的时间复杂度为O(1)，所以整体的时间复杂度为O(n)。

方法心得

1. 分析算法时间复杂度的第一、二步其实可以合并成：直接看谁的执行次数是最高阶的（多为循环结构），算它，再去掉其系数即可。

参考资料：
［1］程杰. 大话数据结构. 北京：清华大学出版社, 2020.
［2］严蔚敏，吴伟民. 数据结构 (C语言版). 北京：清华大学出版社, 1997.