数据结构Day1

小鱼儿 2023-07-06 06:27 84阅读 0赞

/** * Name:test_1.c * Description:数据结构学习程序1 * https://www.bilibili.com/video/av18586085?p=1 * 从P1到P10 的练习代码 * Author:JianshuZhao * Version:V1.0.0 * Date:2020.2.16 */

## 1 算法复杂度 ##

### 1.1 空间复杂度S(n) ###

占用存储单元的长度  
S(n) = C \* n，最终会爆掉

//打印1到n，方式1.
    //S(n) = C * n
    void PrintN(int n)
    { 
    	if (n)
    	{ 
    		PrintN(n - 1);
    		printf("%d\n", n);
    	}
    }

S(n) = C

//打印1到n，方式2
    //S(n) = C
    void PrintN(int n)
    { 
    	for (int i = 0; i < n + 1; i++)
    	{ 
    		printf("%d\n", n);
    	}
    }

### 1.2 时间复杂度T(n) ###

耗费时间的长度  
计算给定多项式在给定点x处的值实现，方式2T（n） C1 \* n^2 + C2 \* n

//计算给定多项式在给定点x处的值实现方式1
    //T（n） C1 * n^2 + C2 * n
    double f1(int n, double a[], double x)
    { 
    	int i;
    	double p = a[0];
    	for (i = 1; i <= n; i++)
    	{ 
    		p += (a[i] * pow(x, i));
    	}
    	return p;
    }

计算给定多项式在给定点x处的值实现，方式2T(n) = C \* n

//计算给定多项式在给定点x处的值实现方式2
    // T(n) = C * n
    double f2(int n, double a[], double x)
    { 
    	int i;
    	double p = a[n];
    	for (i = n; i > 0; i--)
    	{ 
    		p = a[i - 1] + x*p;
    	}
    	return p;
    }

### 1.3 复杂度的比较 ###

最坏情况复杂度Tworst(n)  
平均复杂度Tavg（n）  
Tavg（n）< Tworst(n)，一般分析Tworst(n)。

复杂度的渐进表示法：  
用上界和下界去表示  
下表显示了不同函数随n增长的规模  
![显示了不同函数随n增长的规模][n]  
用图的形式可能要更清楚一些  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]  
上表中有一个错误为，log n应改为nlog n

复杂度分析小窍门：  
1、T上界1(n) + T上界2(n) = max（T上界1(n)，T上界2(n)）  
2、T上界1(n) \* T上界2(n) = T上界(f1n \* f2n)

## 2 最大子列和问题 ##

![在这里插入图片描述][20200216224937496.png]

### 2.1算法1 ###

遍历所有的子列，依次比较最大值

//最大子列和问题算法1
    //T(N) = O(N^3)
    int MaxSubseqSum1(int A[], int N)
    { 
    	int ThisSum, MaxSum = 0;
    	int i, j, k;
    	for (i = 0; i < N; i++)	//i为子列左端位置
    	{ 
    		for ( j = 0;  j < N;  j++)	//j 为子列右端位置
    		{ 
    			ThisSum = 0;
    			for (k= i; k< j; k++)
    			{ 
    				ThisSum += A[k];
    			}
    			if (ThisSum > MaxSum)
    			{ 
    				MaxSum = ThisSum;
    			}
    		}
    	}
    	return 0;
    }

### 2.2 算法2 ###

去除了遍历时，每次都重复相加的项。

//最大子列和问题算法2
    //T(N) = O(N^2)
    int MaxSubseqSum2(int A[], int N)
    { 
    	int ThisSum, MaxSum = 0;
    int i, j, k;
    for (i = 0; i < N; i++)	//i为子列左端位置
    { 
    	ThisSum = 0;
    	for (j = 0; j < N; j++)	//j 为子列右端位置
    	{ 
    		ThisSum += A[j];
    		if (ThisSum > MaxSum)
    		{ 
    			MaxSum = ThisSum;
    		}
    	}
    }
    return 0;
    }

### 2.3分而治之 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]

### 2.4 在线处理 ###

//最大子列和问题算法4，在线处理
    //T(N) = O(N)
    int MaxSubseqSum4(int A[], int N)
    { 
    	int ThisSum, MaxSum = 0;
    	int i;
    	ThisSum = MaxSum = 0;
    	for(i = 0; i < N; i++)	//i为子列左端位置
    	{ 
    			ThisSum += A[j];	//向右累加
    			if (ThisSum > MaxSum)
    			{ 
    				MaxSum = ThisSum;	//发现更大和则更新当前结果
    			}
    			else if (ThisSum < 0)	//当前子列和为负时
    			{ 
    				ThisSum = 0;		//则不可能使后面的部分和增大，抛弃之
    			}
    	}
    	return 0;
    }

[n]: https://img-blog.csdnimg.cn/2020021622394417.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200216224148880.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200216224245999.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200216224937496.png]: https://img-blog.csdnimg.cn/20200216224937496.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200216231055222.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70