• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

浙大MOOC《数据结构》随笔

开发技术 开发技术 3周前 (04-21) 5次浏览

第一讲 基本概念

1.1 什么是数据结构

  1. 图书摆放问题:

    1. 新书如何插入?

      先定类别,再二分查找

    2. 怎么找到指定某本书?

      二分查找

  2. 写程序实现一个函数PrintN

    1. 循环实现

      void PrintN(int N) {
      	int i;
      	for (i = 1; i <= N; i++) {
      		printf("%dn", i);
      	}
      	return;
      }
      
    2. 递归实现

      void PrintN(int N) {
      	if (N) {
      		PrintN(N - 1);
      		printf("%dn", N);
      	}
      	return;
      }
      
    3. 二者对比

      递归的程序对空间的占用有时候可能是非常恐怖的

      上述函数将所占用的空间都占用了还不够,所以就非正常中止。

      得出结论,解题的效率也与占用空间有关

  3. 写程序计算给定多项式在给定x处的值

    1. 硬算

      [% MathType!MTEF!2!1!+-
      % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
      % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
      % 4rNCHbWexLMBbXgBd9gzLbvyNv2CaeHbl7mZLdGeaGqiFv0Je9sqqr
      % pepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs
      % 0-yqaqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaai
      % aabeqaamaabaabauaakeaacaWGMbWaaeWaaeaacaWG4baacaGLOaGa
      % ayzkaaGaeyypa0JaamyyamaaBaaaleaacaaIWaaabeaakiabgUcaRi
      % aadggadaWgaaWcbaGaaGymaaqabaGccaWG4bGaey4kaSIaaiOlaiaa
      % c6cacaGGUaGaey4kaSIaamyyamaaBaaaleaacaWGUbGaeyOeI0IaaG
      % ymaaqabaGccaWG4bWaaWbaaSqabeaacaWGUbGaeyOeI0IaaGymaaaa
      % kiabgUcaRiaadggadaWgaaWcbaGaamOBaaqabaGccaWG4bWaaWbaaS
      % qabeaacaWGUbaaaaaa!59BF!
      fleft( x right) = {a_0} + {a_1}x + … + {a_{n – 1}}{x^{n – 1}} + {a_n}{x^n}
      ]

      double f(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;
      	}
      }
      
    2. 分配律

      [% MathType!MTEF!2!1!+-
      % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
      % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
      % 4rNCHbWexLMBbXgBd9gzLbvyNv2CaeHbl7mZLdGeaGqiFv0Je9sqqr
      % pepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs
      % 0-yqaqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaai
      % aabeqaamaabaabauaakeaacaWGMbWaaeWaaeaacaWG4baacaGLOaGa
      % ayzkaaGaeyypa0JaamyyamaaBaaaleaacaaIWaaabeaakiabgUcaRi
      % aadIhadaqadaqaaiaadggadaWgaaWcbaGaaGymaaqabaGccqGHRaWk
      % caWG4bWaaeWaaeaacaGGUaGaaiOlaiaac6cadaqadaqaaiaadggada
      % WgaaWcbaGaamOBaiabgkHiTiaaigdaaeqaaOGaey4kaSIaamiEamaa
      % bmaabaGaamyyamaaBaaaleaacaWGUbaabeaaaOGaayjkaiaawMcaaa
      % GaayjkaiaawMcaaiaac6cacaGGUaGaaiOlaaGaayjkaiaawMcaaaGa
      % ayjkaiaawMcaaaaa!5D25!
      fleft( x right) = {a_0} + xleft( {{a_1} + xleft( {…left( {{a_{n – 1}} + xleft( {{a_n}} right)} right)…} right)} right)
      ]

      double f(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;
      	}
      }
      
    3. 通过重复运算计算二者计算时长(Tick值),发现前者比后者慢了一个数量级

  4. 所以到底什么是数据结构

    1. 数据对象在计算机中的组织方式

      数据结构有逻辑结构和物理结构

    2. 数据对象必定与一定操作有关,这种操作即为算法

    3. 描述数据结构有个很好的方法“抽象数据类型(Abstract Data Type)”

      1. 数据类型
        1. 数据对象集
        2. 数据集合相关联的操作集
      2. 抽象:描述数据类型的方法不依赖于具体实现
        1. 与存放数据的机器无关
        2. 与数据存储的物理结构无关
        3. 与实现操作的算法和编程语言无关

1.2 什么是算法

  1. 算法(Algorithm)

    • 一个有限指令集
    • 接收一些输入(有些情况不需要输入)
    • 产生输出
    • 一定在有限步骤后终止
    • 每一条指令必须
      • 有充分明确的目标,不可以有歧义
      • 计算机能处理的范围之内
      • 描述应不依赖于任何一种计算机语言以及具体的实现手段
  2. 什么是好的算法

    1. 空间复杂度S(n)

      占用存储单元的长度

      PrintN程序中,循环解法只需要占据固定空间,而递归解法占据N倍空间

    2. 时间复杂度T(n)

      耗费时间的长度

      多项式题目:

      ![image-20210420195835100](C:UsersMr. ChenAppDataRoamingTyporatypora-user-imagesimage-20210420195835100.png)

    考虑复杂度时,一般考虑的是最坏复杂度

    ![image-20210420200053961](C:UsersMr. ChenAppDataRoamingTyporatypora-user-imagesimage-20210420200053961.png)

    若有两段算法分别有复杂度T1(n)=O(f1(n))和T2(n)=O(f2(n)),则

    ​ T1(n)+T2(n)=max(O(f1(n)),O(f2(n)))

    ​ T1(n)*T2(n)=O(f1(n) * f2(n))

    若T(n)是关于n的k阶多项式,那么T(n)=theta(n^k)

    一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度

    if-else结构的复杂度取决于if的条件判断复杂度和分支部分的复杂度,总体复杂度取三者中最大

1.3 最大子列和问题

题目:

给定N个整数的序列{A1,A2,…,An},求函数

[% MathType!MTEF!2!1!+-
% feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbWexLMBbXgBd9gzLbvyNv2CaeHbl7mZLdGeaGqiFv0Je9sqqr
% pepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs
% 0-yqaqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaai
% aabeqaamaabaabauaakeaacaWGMbWaaeWaaeaacaWGPbGaaiilaiaa
% dQgaaiaawIcacaGLPaaacqGH9aqpciGGTbGaaiyyaiaacIhacaGG7b
% GaaGimaiaacYcadaaeWbqaaiaadgeadaWgaaWcbaGaam4Aaaqabaaa
% baGaam4Aaiabg2da9iaadMgaaeaacaWGQbaaniabggHiLdGccaGG9b
% aaaa!5389!
fleft( {i,j} right) = max { 0,sumlimits_{k = i}^j {{A_k}} }
]

的最大值。

算法1-暴力求解法

int MaxSubseqSum1(int A[], int N) {
	int ThisSum, MaxSum = 0;
	int i, j, k;
	for (i = 0; i < N; i++) {
		for (j = i; j < N; j++) {	//遍历所有f(i,j)
			ThisSum = 0;
			for (k = i; k <= j; k++)	//计算求和函数
				ThisSum += A[k];
				if (ThisSum > MaxSum)	//MaxSum更新
					MaxSum = ThisSum;
		}
	}
	return MaxSum;
}

算法复杂度:O(N^3)

算法2-递加

int MaxSubseqSum1(int A[], int N) {
	int ThisSum, MaxSum = 0;
	int i, j, k;
	for (i = 0; i < N; i++) {
		ThisSum = 0;
		for (j = i; j < N; j++) {	//每次循环一次,就加一次,没必要每次都从头开始加
			ThisSum += A[j];
			if (ThisSum > MaxSum)
				MaxSum = ThisSum;
		}
	}
	return MaxSum;
}

算法复杂度:O(N^2)

算法3-分而治之

4 -3 5 -2 -1 2 6 2

4 5 2 6

​ 6 8

​ 11

算法复杂度:O(NlogN)

算法4-在线处理

int MaxSubseqSum1(int A[], int N) {
	int ThisSum, MaxSum = 0;
	int i;
	ThisSum = MaxSum = 0;
	for (i = 0; i < N; i++) {
		ThisSum += A[i];	//向右累加
		if (ThisSum > MaxSum) {
			MaxSum = ThisSum;	//发现更大和则更新当前结果
		}
		else if (ThisSum < 0) {	//如果当前子列和为负数
			ThisSum = 0;	//则不可能使和后面的部分和增大,抛弃之(关键是此时MaxSum不变!)
		}
	}
	return MaxSum;
}

算法复杂度:O(N)


程序员灯塔
转载请注明原文链接:浙大MOOC《数据结构》随笔
喜欢 (0)