数据结构与算法学习日记【1】

解决问题方法的效率,跟算法的巧妙程度有关。

什么是数据结构?

定义

1、数据对象在计算机中的组织方式⬇️

  • 逻辑结构
  • 物理存储结构

2、数据对象与一系列加在其身上的操作相关
3、完成上述操作所用的方法即为算法

抽象数据类型(Abstract Data Type)

1、数据类型

  • 数据对象集
  • 数据集合相关的操作集(编程语言封装的类)

2、抽象

  • 跟存放数据的机器没有关系
  • 跟数据的物理存储结构无关
  • 与程序的算法和编程语言无关

只描述数据对象集和相关操作是什么,不涉及如何做到的问题

什么是算法

定义

算法(Algorithm)

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

      算法的复杂度

  • 时间复杂度——S(n)
    程序执行占用存储单元的长度
  • 空间复杂度——T(n)
    程序执行所耗费时间的长度

好算法的取决

常关注的两种复杂度

  • 最坏情况复杂度
    Tworst(n)
  • 平均复杂度
    Tavg(n) <= Tworst(n)

复杂度分析

  • 两段算法分别有复杂度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) = Φ(n^k^)
  • 一个for循环的时间复杂度等于循环次数乘循环体代码的复杂度
  • if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度,总体复杂度取三者中最大

应用实例(最大子数列)

算法一

  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int MaxSubseqSum1( int A[], int N )
{ int ThisSum, MaxSum = 0;
int i, j, k;
for( i = 0; i < N; i++ ) { /* i是子列左端位置 */
for( j = i; j < N; j++ ) { /* j是子列右端位置 */
ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和 */
for( k = i; k <= j; k++ )
ThisSum += A[k];
if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大 */
MaxSum = ThisSum; /* 则更新结果 */
} /* j循环结束 */
} /* i循环结束 */
return MaxSum;
}
  • 时间复杂度
    T(n) = O(N^3^)

    算法二

  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int MaxSubseqSum2( int A[], int N )
{ int ThisSum, MaxSum = 0;
int i, j;
for( i = 0; i < N; i++ ) { /* i是子列左端位置 */
ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和 */
for( j = i; j < N; j++ ) { /* j是子列右端位置 */
ThisSum += A[j];
/*对于相同的i,不同的j,只要在j-1次循环的基础上累加1项即可*/
if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大 */
MaxSum = ThisSum; /* 则更新结果 */
} /* j循环结束 */
} /* i循环结束 */
return MaxSum;
}
  • 时间复杂度
    T(n) = O(n^2^)

    算法三(分而治之)

    算法四(线上/在线处理)

  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
int MaxSubseqSum4( int A[], int N )
{ int ThisSum, MaxSum;
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; /* 则不可能使后面的部分和增大,抛弃之 */
}
return M
}