数据结构与算法分析-第一章-引论

数据结构与算法分析-第一章-引论

文章目录

• 数据结构与算法分析-第一章-引论
• • 1.2 数学知识复习
  • 1.3 递归简论
  • 第一章习题
  • • 1.1选择问题（k=N/2）
    • 1.2字谜游戏问题
    • 1.3输出任意实数
    • 1.4输出文件
    • 1.6级数求和问题
• 结尾

数据结构与算法分析-第一章-引论

本文是数据结构与算法分析（c语言描述）原书第二版的读书笔记，选择此书的原因旨在学习算法的同时巩固自己的数据结构知识（大一下学的有些东西遗忘了）

算法实现永远的原则：

正确性>时间复杂度>空间复杂度（极少数情况下，三者可互换，比如NP完全问题这类特殊情况等，可以牺牲正确性，以近似最优解的方式来换取更好的时间复杂度）

1.2 数学知识复习

定理1.1
l o g A B = l o g C B l o g C A log_A{B}=frac{log_C{B}}{log_C{A}} logA​B=logC​AlogC​B​
据此思考其实c中所有与对数相关的数都可以使用log和log10实现

#include$int\; main()\{\; //double\; log(double\; x)以e为底数\; //double\; log10(double\; x)以10为底数\; printf("\%lf",log(100));\; printf("\%lf",log10(100));\; printf("\%lf",log(8)/log(2));//利用换底公式\; \}$

模同余记号

A ≡ B ( m o d   N ) Aequiv B(mod N) A≡B(mod N)

1.3 递归简论

注意运算中mod *** 作的开销是比较大的

N   m o d   x = N − ⌊ N / x ⌋ x N mod x=N-lfloor N/xrfloor x N mod x=N−⌊N/x⌋x

第一章习题 1.1选择问题（k=N/2）

给定一组数据，输出第k大的数

数据使用随机生成的random_array.txt文件（大小自选）

• 思路1：直接快速排序输出结果

  void quick_sort(int *array,int left,int right){
  	if(left>=right)
  	return;
  	int i,j,x;
  	i=left;
  	j=right;
  	x=array[i];
  	while(i=x&&i 

• 思路2：当数组范围比较小的时候，直接采用hash表

  int hash[maxsize]={0};
  	for(i=0;i=k){
  			printf("%dn",i);
  			break;
  		}
  	}
  

• 思路3：利用快排算法中的挖坑法思想（不考虑两侧数组的排序）

  int quick_sort_k(int *array,int left,int right,int target){//保证两侧数组 
  	if(left==right)
  	return left;
  	int i,j,x;
  	i=left;
  	j=right;
  	x=array[i];
  	while(i=x&&itarget)
  	return quick_sort_k(array,left,i-1,target);
  	else
  	return quick_sort_k(array,i+1,right,target);
  }
  

算法复杂度比较

正确性空间复杂度时间复杂度200万数据集运行时间/ms特点快排True O ( N ) O(N) O(N) O ( N l o g 2 N ) O(Nlog_2{N}) O(Nlog2​N)3986时间复杂度过高hash表True O ( m a x ( a r r a y [ i ] ) ) O(max(array[i])) O(max(array[i])) O ( N ) O(N) O(N)4时间复杂度为线性但是空间复杂度过高（可能）快排思想挖坑法True O ( N ) O(N) O(N) ? ? ?44思想优秀，而且比起hash表更具有普遍适用性 1.2字谜游戏问题

题干：（如图）

思考了一下，只想到了最最原始的暴力求解算法，不知道提示里的快速算法是怎么实现的？

• 暴力for嵌套（训练自己思路的清晰程度）

  #define MAXSIZE 100
  #define DIRECTION 4
  #define ARRAYSIZE 4
  #define DICTSIZE 4//字典大小 
  #define WORDSIZE 10//单词最长长度 
  char array[4][4] = {
      { 't', 'h', 'i', 's' },
      { 'w', 'a', 't', 's' },
      { 'o', 'a', 'h', 'g' },
      { 'f', 'g', 'g', 't' }
  };                                                        //字谜
  char *dict[DICTSIZE] = { "this", "two", "fat", "that" }; //字典
  char *result[MAXSIZE];
  int count=0;
  clock_t start,end;
  void init(){
  	int i;
  	for(i=0;i
   
  提示里的巧妙算法（暂时不知道如何实现）
   

1.3输出任意实数

整数直接输出，但是浮点数可要考虑考虑如何精准输出（虽然可以直接使用char解决，但是此题不允许）

关于(int)取整问题：向0取整

• 方法：末尾添加0.5，解决了浮点数存储不精确的问题，注意要先处理进位问题，否则进位无法跨界传递。

  并且添加了inf用于处理1.2345 3这类问题

  #define inf 1e-15
  void print_digit(double x,int len){
  	int integer;//整数部分 
  	int i;
  	double fraction;//小数部分 
  	double tmp=0.5;
  	
  	if(x<0){//处理正负问题
  		printf("-");
  		x=-x;
  	}
  	
  	i=0;
  	while(i 

1.4输出文件

题干：c提供如#include filename这样的语句，编写一个程序，使它读入被include修饰的一个文件并输出这个文件

懒得写（貌似无法利用c语言实现）；

1.6级数求和问题

计算级数
∑ i = 0 ∞ i N 4 i sum_{i=0}^inftyfrac{i^N}{4^i} i=0∑∞​4iiN​
利用交叉相减：使用 i N − ( i − 1 ) N = O ( i N − 1 ) i^N-(i-1)^N=O(i^{N-1}) iN−(i−1)N=O(iN−1)化简等式

结尾

可恶的算法啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊。。。。。卒