数据结构和算法笔记——基础知识

函数渐进增长

  • 函数的渐进增长:给定两个函数g(n)和g(n),如果存在整数N使得对于所有n>N,总有f(n)比g(n)大,那么我们说f(n)的增长渐进快于g(n)
  • 在渐进增长中,加法常数不影响最终的算法变化曲线
  • 与最高次项相乘的常数也并不重要
  • 最高次项指数大的,随着n的增长,结果也会增长的特别快
  • 判断一个算法的效率时,函数中的常数和其他次要项常常可以忽略不计,重点关注最高阶项的阶数

时间复杂度

  • T(n) = O(f(n))
  • 语句总的执行次数T(n)关于输入规模n的函数
  • 分析T(n)随n的变化情况并确定n的数量级
  • 它表示随问题规模的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进复杂度
  • 大O记法:O()
  • 一般情况下,随着n增大,T(n)增长最慢的算法为最优算法

推导大O阶的方法

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

常数阶举例

  • 多条打印语句,O(1)

线性阶

  • 单层循环结构,O(n)

平方阶

  • 嵌套循环结构,m层嵌套时间复杂度为O(n^m)
int i, j, n = 100;
for(i=0; i<n; i++){
    for(j=i; j<n; j++){
        printf("print something")
    }
}

以上算法的执行次数为n+(n-1)+(n-2)+…+1=n(n+1)/2
化简为n2/2+n/2得O(n2)

对数阶

int i = 1, n = 100;
while(i < n){
    i = i * 2;
}

2^x = n, x=log(2)n(log以2为底的n),这个循环的时间复杂度为O(logn)

函数调用的时间复杂度分析

  • 与之前平方阶类似,主要关注被调用函数的时间复杂度

常用的时间复杂度

  • 常数阶
    • O(1)
  • 线性阶
    • O(n)
  • 平方阶
    • O(n^2)
  • 对数阶
    • O(logn)
  • nlogn阶
    • O(nlogn)
  • 立方阶
    • O(n^3)
  • 指数阶
    • O(2^n)

常用的时间复杂度耗费的时间从小到大排序

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

最坏情况与平均情况

  • 平均情况就是期望的运行时间
  • 现实意义最大的是算法在最坏情况下的运行时间

空间复杂度

  • S(n) = O(f(n))
    • n:问题输入规模
    • f(n):关于n占用的存储空间的函数

抽象数据类型(Abstract Data Type, ADT)

  • 数据类型:一组性质相同的值的集合和定义在此集合上的一些操作
    • 原子类型:不可再分的基本类型
    • 结构类型:由若干类型组合而成,可以再分解的类型
  • 抽象:是指取出事物具有普遍性的本质而忽略非本质的细节,是对具体事物的一个概括
  • 抽象数据类型:
    • 指一个数学模型及定义在该模型上的一组操作
    • 抽象数据类型的定义仅取决于它的一组逻辑特性,而与其在计算机中如何表示和实现无关

    描述抽象数据类型的标准格式:

      ADT 抽象数据类型名
      Data
          数据元素之间逻辑关系的定义
      Operation
          操作
      endADT
    
    原文作者:一把把拉普拉斯拉住
    原文地址: https://blog.csdn.net/pikachu_12138/article/details/96204408
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞