数据结构概述

Wu Jun 2020-03-20 16:14:09
Categories: > > Tags:

程序设计 = 数据结构 + 算法

1 数据结构

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

1.1 基本概念

graph TD
数据-->数据对象
数据对象-->数据元素1
数据元素1-->数据项1
数据元素1-->数据项2
数据对象-->数据元素2
数据元素2-->数据项3
数据元素2-->数据项4

1.2 逻辑结构和物理结构

逻辑结构

数据对象中数据元素之间的相互关系。

物理结构

数据的逻辑结构在计算机中的存储形式

2 算法

算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。

2.1 算法的特性

算法具有五个基本特性

2.2 算法设计的要求

2.3 算法时间复杂度

推导大 O 阶方法

n 是问题规模,对数列运算出执行次数T(n) = O(f(n))

常见的时间复杂度排序: O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

最坏情况与平均情况

没有特殊说明的情况下,都指最坏时间复杂度

2.4 算法空间复杂度

S(n) = O(f(n))。

若算法执行时所需的辅助空间对于输入量而言是个常数,则称此算法为原地工作,空间复杂度 O(1)。