数据结构和算法的基本概念和术语

一、数据结构的基本概念

1. 数据:

描述客观事物的符号, 是计算机中可以操作的对象, 是被计算机识别, 并输入给计算机处理的符号集合.

数据不仅仅包括整型,实型等基本数据结构, 还包括网页, 音频, 视频, 图片等

2. 数据元素

组成数据的, 有一定意义的基本单位, 在计算机中通常作为整体处理, 也被称为记录.

比如:

  • 把人类当做数据, 那么数据元素就是每一个人.
  • 把禽畜当做数据, 那么牛, 马, 羊,鸡等就是数据元素。

3.数据项

一个数据元素是有若干个数据项组成的, 数据项是数据不可分割的最小单位

比如人是数据元素, 那么人身上的眼, 耳, 鼻,嘴等就是数据项

4.数据对象

性质相同的数据元素的集合, 时数据的子集。
可以理解为数据

5.数据结构

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

结构, 简单的理解就是关系, 比如分子结构,就是说组成分子的原子之间的排列方式。 不同的数据元素之间不是独立的, 而是存在特定的关系,我们将这些关系称为结构

按视点的不同, 我们把数据结构分为逻辑结构和物理结构。

逻辑结构

是指数据对象中数据袁术之间的互相关系

  1. 集合结构
  2. 线性结构
  3. 树形结构
  4. 图形结构

物理结构

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

  1. 顺序存储结构: 排队形式
  2. 链式存储结构: 指针的形式

二、算法的基本概念

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

算法的特性: 有穷性,确定性, 可行性, 输入, 输出。

算法的设计要求: 正确性, 可读性, 健壮性, 高效率, 和低存储量需求

算法的度量方法:

  1. 事后统计方法 (不科学, 不准确, 因为不同的计算机硬件, 内存, 平台的因素影响)
  2. 事前分析估算方法

函数的渐进增长: 给定两个函数 f(n) 和 g(n), 如果存在一个整数 N , 使得对于所有的 n > N, f(n)总是比 g(n)大, 那么, 我们说f(n)的增长渐进快于g(n)。 于是我们可以得出一个结论, 判断一个算法好不好, 我们只通过少量的数据是不能作出准确判断的, 如果我们可以对比算法的关键执行次数函数的渐进增长性, 基本就可以分析出: 某个算法, 随着n的变大, 它会越来越优于另一算法, 或者越来越差于另一算法。

然后给出了算法事件的复杂度的定义和推导大 O 阶的步骤。

推导大 O 阶:

  • 用常数 1 取代运行时间中的所有加法常熟
  • 在修改的运行次数函数中, 只保留最高阶的常数
  • 如果最高阶项存在且不是 1 , 则去除与这个项相乘的常数

得到的结果就是 大O阶。

常见的事件复杂度所耗时间的大小排列:
O(1) < O(logn) < O(n) < O(nlogn) < O(n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容