《数据结构》chap1 绪论 Introduction

🌺博客汇总：🌃Summary And Schedule🌠

🌸考研相关内容汇总：考研Schedule&&Summary

🌼408王道《数据结构》课程目录：

考纲：

算法时间复杂度和空间复杂度的分析和计算

本章需要掌握：

1、数据结构基础概念：数据、数据元素、数据对象、数据类型、数据结构
2、数据结构三要素：逻辑结构、存储结构、数据的计算
3、算法（特性5，“好”4）、程序
4、T(n)，常对幂指阶，设最高频次语句执行k次
5、S(n)，递归=深度、O(1)不使用额外空间

1、Data Structure Basic Concepts

1.1 Data

数据：数据是信息的载体

1.2 Data Elements、Data item

数据元素：是数据的基本单位

数据项：是构成数据元素不可分割的最小单位

1.3 Data Object

数据对象：是具有相同性质的数据元素的集合

1.4 Data Structure

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合

1.5 Data Type

数据类型：是一个值的集合和定义在此集合上的一组操作的总称。

（1）原子类型：值不可再分的数据类型

（2）结构类型：值可再分的数据类型

（3）抽象数据类型(Abstract Data Type，ADT)：一个数学模型及定义在该数学模型上的一组操作。

2、Data Structure

三要素

2.1 Logical Structure

逻辑结构：是指数据元素之间的逻辑关系

2.2 Stroage Structure

存储结构：是指数据结构在计算机中的表示，也称物理结构（Phyical Structure）

2.3 Data Calculation

运算的定义是针对逻辑结构的，指出运算的功能

运算的实现是针对存储结构的，指出运算的具体操作步骤

3、Algorithm

算法：是对特定问题求解步骤的一种描述

3.1 五个特性

1、有穷性：有穷时间完成

2、确定性：相同输入对应相同输出

3、可行性：执行有限次基本运算

4、输入：零或多个输入

4、输出：一或多个输出

3.2 “好”算法指标

1、正确性：正确解决问题

2、可读性：加注释帮人理解

3、健壮性：处理非法数据

4、高效率与低存储需求：效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关

4、Time Complexity

时间复杂度：所有语句的频度（执行次数）之和。 T(n)=O(f(n))
$$
0(1)\text{＜}0(log_2n)\text{＜}0(n) \text{＜}O(nlog_2n) \text{＜}0(n^2) \text{＜}0(n^3)\text{＜}O(2^n)

<O(n!)
$$
时间复杂度的计算忽略高阶项系数和低阶项

5、Space complexity

空间复杂度：会判断是不是O(1)就可以了，空间复杂度O(1)的意思是，n个元素排序，不使用额外的空间（随着n增长而增长的空间）。 S(n)=O(f(n))。递归深度记作空间复杂度。

6、Wrong Question

细节错误

1、注意问的是执行次数还是时间复杂度

2、不一定只有一个问题规模，可能同时存在m、n

// T(n)=O(m*n)
for(i=0;i<n;i++)
  for(j=0;j<m;j++)
    count++;

概念错误

1、数据的逻辑结构独立于其存储结构（逻辑结构是从面向实际问题的角度出发，只采用抽象表达方式，独立于存储结构）

2、T(n)取决于问题的规模和待处理数据的初态（可能存在0，计算快）

一般错误

1、设count++执行x次（等比数列求和），第一个for循环执行k次（k~logn）

// T(n)=O(n)
for(i=1;j<n;i*=2)
  for(j=0;j<i;j++)
    count++;

2、看错了？好简单（题目换了几个字母看着有点乱，或者头脑不醒）

// T(n)=O(nlogn)
for(i=1;i<n;i*=2)
  for(j=0;j<n;j++)
    count++;

3、merge()时间复杂度O(n)，归并排序mergesort(1,n)时间复杂度是？

这个可能一开始不好理解，可以上网搜归并排序看看图

f(n)=2f(n/2)+n=…=2^kf(n/2^k)+kn，令n=2^k带入解出

// T(n)=O(nlogn)
void mergesort(int i,int j)
{
  int m;
  if(i!=j)
  {
    m = (i+j)/2;
    mergesort(i,m);
    mergesort(m+1,j);
    merge(i,j,m);
  }
}

4、设计一个算法，平均比较次数小于3n/2，找出数组A[0,…,n-1]最大值和最小值

（注意平均，数组从小到大排序比较最多2(n-1)次，数组从大到小排序比较最少(n-1)次，平均3(n-1)/2）

void maxmin(int A[],int n)
{
  int i,max,min;
  max=A[0];min=A[0];
  for(i=1;i<n;++i)
	if(A[i]>max)
      max=A[i];
	else if(A[i]<min)
      min=A[i];
  printf("最大值:%d，最小值:%d",max,min)
}