程序员:数据结构与算法,逻辑结构、物理结构和时间复杂度

黑板报 2019-12-17

程序员:数据结构与算法,逻辑结构、物理结构和时间复杂度

数据结构

数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。

为什么要学习数据结构?

学习数据结构学习的是逻辑思维和抽象思维的能力。程序设计=数据结构+算法,底层和源码的开发更是离不开数据结构。想要学的更深入就要学习数据结构。

什么是数据结构?

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

数据结构的逻辑结构与物理结构

数据结构的逻辑结构是指数据元素之间的相互关系,逻辑结构分为以下四种:

  • 集合结构:集合中的数据结构除了同属于一个集合外,它们之间没有其他关系
  • 线性结构:线性结构中的数据元素之间是一对一的关系
  • 树形结构:树形结构中的数据元素之间存在一种一对多的层次关系
  • 图形结构:图形结构的数据元素是多对多的-关系

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

  • 顺序存储结构;开辟一组连续的空间存储数据,通常用数组来实现,数组中空间本身是连续的,保证了数据之间的关系
  • 链式存储结构:开辟一组随机的空间存储数据,通常用节点来实现,节点不仅要存储数据,还要存储 下一节点的位置以保证数据之间的关系

我们要根据应用场景的不同灵活选择最合适的数据结构

程序员:数据结构与算法,逻辑结构、物理结构和时间复杂度

算法

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

怎么评价一个算法的好坏?

事后统计方法:通过设计好的程序和数据,利用计算机计时器对不同算法程序的运行时间进行比较,从而确定算法效率的高低

事前分析估算法:在计算机程序编制前,依据统计方法对算法进行估算,一个程序在计算机上运行时所消耗的时间取决下列因素:

  • 算法采用的策略和方法
  • 编译产生的代码质量
  • 问题的输入规模
  • 机器执行指令的执行速度

时间复杂度

时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。

在进行算法时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随 n 的变化情况并确定T(n)的数量级,算法时间复杂度,也就是时间度量,记作:T(n)= O(f(n))。

它表示随问题规模 n 的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称时间复杂度。

其中f(n)是问题规模n的某个函数。

T(n)是具体的次数,O(n)不是具体的执行数,看增长率。

常见的几个时间复杂度

  • 常数阶O(1) 没有循环
  • 对数阶O(logn) 有循环,加速度减小的加速运动
  • 线性阶O(n) 循环情况
  • nlogn阶 O(nlog n) 二叉树里用
  • 平方阶O(n^2)
  • 立方阶O(n^3)
  • 指数阶O(2^n)

时间复杂度从上到下增大

我们考虑的时间复杂度都是最坏情况

程序员:数据结构与算法,逻辑结构、物理结构和时间复杂度

相关推荐

bluewelkin / 0评论 2020-02-02