浏览量: 109 次浏览

数据结构与算法概述

2020年1月17日 0 作者 Nie Hen

算法就是去解决一个问题的方法或者是 一个思路 一种思想等
目的就是解决问题。
算法是相当重要的,如果把问题理解成战争的话,算法就是兵法

算法的提出

算法的概念

算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。
一般地,当算法在处理信息时,会从输入设备或数据的存储地址读取数据,把结果写入输出设备或某个存储地址供以后再调用。

算法的特性
  1. 输入: 算法具有0个或多个输入
  2. 输出: 算法至少有1个或多个输出
  3. 有穷性: 算法在有限的步骤之后会自动结束而不会无限循环,并且每一个步骤可以在可接受的时间内完成
  4. 确定性:算法中的每一步都有确定的含义,不会出现二义性
  5. 可行性:算法的每一步都是可行的,也就是说每一步都能够执行有限的次数完成

算法是独立存在的一种解决问题的方法和思想。

算法效率均衡

根据算法 程序的运行时间可以反映出算法的效率

时间复杂度与“大O记法”

由于不同的机器 硬件性能不同 相同的程序运行的时间 也会不一样 因此使用运行时间来做标准显然是不合适的 。
所以需要一个客观的标准来评判算法的优劣

大O记法”:对于单调的整数函数f,如果存在一个整数函数g和实常数c>0,使得对于充分大的n总有f(n)<=c* g(n),就说函数g是f的一个渐近函数(忽略常数),记为f(n)=O(g(n))。也就是说,在趋向无穷的极限意义下,函数f的增长速度受到函数g的约束,亦即函数f与函数g的特征相似。

时间复杂度:假设存在函数g,使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n)),则称O(g(n))为算法A的渐近时间复杂度,简称时间复杂度,记为T(n)

简单理解 :对于算法的时间性质和空间性质,最重要的是其数量级和趋势,这些是分析算法效率的主要部分。。例如,可以认为3n2和100n2属于同一个量级,如果两个算法处理同样规模实例的代价分别为这两个函数,就认为它们的效率“差不多”,都为n2级

时间复杂度分类
  1. 算法完成工作最少需要多少基本操作,即最优时间复杂度
  2. 算法完成工作最多需要多少基本操作,即最坏时间复杂度
  3. 算法完成工作平均需要多少基本操作,即平均时间复杂度

主要关注的就是最坏时间复杂度
最优时间复杂度没有意义 平均时间复杂度难以保证而且不易计算

时间复杂度的几条规则
  1. 基本操作,即只有常数项,认为其时间复杂度为O(1)
  2. 顺序结构,时间复杂度按加法进行计算
  3. 循环结构,时间复杂度按乘法进行计算
  4. 分支结构,时间复杂度取最大值
  5. 判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略
  6. 在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度
常见时间复杂度

enter description here

常见时间复杂度之间的关系
enter description here

数据结构

概念

数据结构就是数据存储的方式

数据是一个抽象的概念,将其进行分类后得到程序设计语言中的基本类型。如:int,float,char

Python给我们提供了很多现成的数据结构类型,这些系统自己定义好的,不需要我们自己去定义的数据结构叫做Python的内置数据结构,比如list dict tuple

而有些数据组织方式,Python系统里面没有直接定义,需要我们自己去定义实现这些数据的组织方式,这些数据组织方式称之为Python的扩展数据结构,比如栈,队列等。

算法与数据结构的区别

算法是为了解决实际问题而设计的,数据结构是算法需要处理的问题载体

数据结构只是静态的描述了数据元素之间的关系。

高效的程序需要在数据结构的基础上设计和选择算法。

最常用的数据运算

有五种:
– 插入
– 删除
– 修改
– 查找
– 排序

else

知乎 算法从入门到“放弃
B站 python数据结构与算法学习