Java笔记 · · By/蜜汁炒酸奶

数据结构与算法小结01-复杂度01

数据结构

  • 线性结构:数组、链表,栈、队列、哈希表
  • 树:二叉树、二叉堆
  • 图等复杂数据结构

时间复杂度

  • 表示代码执行时间随数据规模增长的变化趋势,也叫渐进时间复杂度,简称时间复杂度
  • 对一个算法运行时间的度量。
  • 所有代码的执行时间T(n) 与 每行代码的执行次数f(n) 成正比。
  • 常见的时间复杂的从低到高的顺序,包含:O(1),O(logn)、O(n)、O(nlogn)、O(n^2)

大O时间复杂度表示法

T(n) = O(f(n))
  • T(n) 表示 代码执行的时间
  • n 表示数据规模的大小
  • f(n) 表示每行代码执行的次数总和,因为是一个公式,所以用 f(n) 来表示。
  • O 表示代码的执行时间 T(n) 与 f(n) 表达式 成正比关系。
  • 当n很大时,公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。

时间复杂度分析方式

  1. 只关注循环执行次数最多的一段代码:分析一个算法、一段代码的时间复杂度时,只关注循环执行次数最多的一段即可。
  2. 加法法则:总的时间复杂度等于量级最大的那段代码的时间复杂度。 若 T1(n)=O(f(n)),T2(n)=O(g(n));那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))
  3. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。若 T1(n)=O(f(n)),T2(n)=O(g(n));那么 T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))

复杂度量级

  • 常量阶 O(1)
  • 对数阶 O(logn)
  • 线性阶 O(n)
  • 线性对数阶 O(nlogn)
  • 平方阶 O(n^2)、立方阶 O(n^3) … K次方阶 O(n^n)
  • 指数阶 O(2^n)
  • 阶乘阶 O(n!)

大致可分类两类:多项式量级非多项式量级

非多项式量级只有两个:O(2^n)O(n!)

时间复杂度为非多项式的算法问题叫做 NP(Non-Deterministic Polynomial,非确定多项式) 问题。

当数据规模 n 越来越大时,非多项式量级算法的执行时间回急剧增加,求解问题的执行时间会无线增长。所以非多项式时间复杂度的算法是非常低效的算法。

常见的多项式时间复杂度

O(1)

一般情况下,只要算法中不存在循环、递归语句(意味着代码的执行时间不随 n 的增大而增长),即使有上万行代码,其时间复杂度也是O(1)

O(logn)、O(nlogn)

所有对数阶的时间复杂度都可以记为 O(logn),原因是:

  • 对数之间是可以相互转换的, 通过换底公式可得 log3n = log32 * log2n
  • 所以 O(log3n) = O(C * log2n),C = log32
  • 根据大O时间复杂度表示法,系数可以忽略,故 O(log3n) = O(log2n)
  • 因此,在对数阶时间复杂度的表示方法里,我们忽略对数的“底”,统一表示为 O(logn)
  • 如果一段代码的时间复杂度是 O(logn),我们循环执行 n 遍,时间复杂度就是 O(nlogn)
  • 归并排序、快速排序的时间复杂度都是 O(nlogn)

O(m+n)、O(m*n)

  • m 和 n 是表示两个数据规模,比如一段段代码中两个并列循环。无法评估谁的量级更大,所以不能通过加法原则简单省略其中一个,所以此时代码的时间复杂度是 O(m+n)
  • 加法规则需要改为:T1(m) + T2(n) = O(f(m) + g(n))
  • 乘法法则继续有效:T1(m)*T2(n) = O(f(m) * f(n))

空间复杂度

  • 对一个算法运行过程中临时占用存储空间大小的度量
  • 表示算法的存储空间与数据规模直接的增长关系,全称渐进空间复杂度。
  • 从低到高的顺序:O(1)、O(n)、O(n^2)等。
  • O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到
  • 递归的空间复杂度和递归深度成正比。

参考资料

数据结构与算法之美

评论已关闭

example
C
蜜汁炒酸奶

当前处于试运行期间,可能存在不稳定情况,敬请见谅。

欢迎点击此处反馈访问过程中出现的问题