程序员社区

数据结构(算法)ps如果有新内容会补充

算法:

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

特性:

  1. 输入
  2. 输出
  3. 有穷性
  4. 确定性
  5. 可行性

算法设计要求

 

  1. 正确性
  2. 可读性(算法设计的另一目的是为了便于阅读,理解和交流)
  3. 健壮性(当输入数据不合法时,算法也能做出相应处理,而不是产生异常或者莫名其妙的结果)适用于高级算法,像蓝桥杯竞赛还没这么要求过
  4. 时间效率高(利用率高)和储存量低(在算法竞赛的时候,一道题有很多解,但是它会要求时间和内存,所以暴力解法往往会超时)

算法设计的基本方法

列举法、归纳法、递推、递归、减半递推技术、回溯法。

 

算法效率的度量方法

  1. 事后统计法:主要通过设计好的测试程序和数据,利用计算机计时器对不同算法编制的程序运行时间进行比较,从而确定算法效率的高低。
  2. 事前分析估算法:在计算机程序编制前,依据统方法对算法进行估算。
  • 一个程序的运行时间,依赖于算法好坏和输入规模。
  • 在分析程序的运行时间时,最重要的时把程序看成是独立程序设计语言的算法一系列步骤

函数的渐近增长:给定俩个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么我们说f(n)的渐近增长快于g(n)

 

判断一个算法的效率

函数的常数和其他次要的数据项可以忽略,而更应该关注主项(最高阶项)的阶数

算法的时间复杂度

算法的时间量度,记作:T(n)=O(f(n))   

他表示随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度,其中f(n)是问题规模n的某个函数。

推导大O阶方法

  1. 用常数1取代运行时间中的所有加法常数
  2. 在修改后的运行次数函数中,只保留最高项。
  3. 如果最高阶项数存在且不是1,则除去与这个项相乘的常数,得到的就是大O阶
  • 常数阶  O[1]  固定次数
  • 线性阶  O[n]  for循环
  • 对数阶  O[logn]    *=
  • 平方阶  O[n2]   嵌套for
  • nlogn阶  递归的复杂度  T(n) = O(nlogn)  推导网站: https://www.cnblogs.com/hlongch/p/5749038.html
  • 指数阶  O[2 n]

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

 

最坏情况与平均情况

  • 最坏情况是运行时间的一种保证,那就是运行时间不会再坏了,在应用中这是一种最重要的需求,通常,除非特别指定,我们提到的运行时间都是最坏情况的运行时间。
  • 平均运行时间是所有情况中最有意义的,他是期望的运行时间。

算法的空间复杂度

公式:  S[n]=O(f[n])  其中n为规模,f(n)为语句关于n所占存储空间的函数

 

算法的优劣直接决定了程序的运行效率

愚公移山 :手挖

现代移山: 炸药

 

 

排序类型 排序方法 最坏情况下 最好情况下 说明
交换排序 冒泡排序 时间复杂度n2 n(n-1)/2 最简单的交换排序。在待排序的元素序列基本有序的前提下,效率最高
快速排序 n(n-1)/2 O(Nlog2 N)  
插入排序 简单插入排序 n(n-1)/2  每个元素距其最终位置不远时适用
希尔排序 O(n1.5)  
选择排序 简单选择排序 n(n-1)/2  
堆排序   O(nlog2n)  适用于较大规模的线性表

冒泡排序算法在最好的情况下的元素交换次数为 0 。
 在最坏情况下,冒泡排序的时间复杂度为 n(n-1) /2 。
对于长度为n的线性表,在最坏情况下,快速排序所需要的比较次数为 n(n-1) /2 。
在最坏情况下,简单插入排序需要比较的次数为 n(n-1) /2 。
在最坏情况下,希尔排序需要比较的次数为 O(n1.5) 。注:括号里是n的1.5次方。
 在最坏情况下,简单选择排序需要比较的次数为 n(n-1) /2 。
 在最坏情况下,堆排序需要比较的次数为 o(nlog2n) 。
对于输入为N个数进行快速排序算法的平均时间复杂度是 O(Nlog2 N)。

 

 

不使用比较运算符求俩个数的最大值和最小值

max = (a+b+Math.abs(a-b))/2;

min = (a+b-Math.abs(a-b))/2;

 

 

 

 

 

                     清平调

云想衣裳花想容,春风拂槛露华浓。

若非群玉山头见,会向瑶台月下逢。

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 数据结构(算法)ps如果有新内容会补充

一个分享Java & Python知识的社区