gitbook-way-to-algorithm
  • Introduction
  • Preface 前言
  • Content 目录
  • MathSymbolTable 数学符号表
  • Chapter-1 BasicKnowledge 第1章 基础知识
    • TimeComplexity 时间复杂度
    • Recursion 递归式
  • Chapter-2 Sort 第2章 排序
    • InsertSort 插入排序
    • BubbleSort 冒泡排序
    • QuickSort 快速排序
    • MergeSort 归并排序
  • Chapter-3 Search 第3章 搜索
    • BinarySearch 二分查找法(折半查找法)
    • AdditionMultiplicationPrinciple 加法乘法原理
    • BruteForce 暴力枚举
    • Recursion 递归
    • BreadthFirstSearch 广度优先搜索
    • BidirectionalBreadthSearch 双向广度搜索
    • AStarSearch A*搜索
    • DancingLink 舞蹈链
  • Chapter-4 DataStructure 第4章 数据结构
    • DisjointSet 并查集
    • PrefixTree(TrieTree) 前缀树
    • LeftistTree(LeftistHeap) 左偏树(左偏堆)
    • SegmentTree 线段树
    • FenwickTree(BinaryIndexedTree) 树状数组
    • BinarySearchTree 二叉查找树
    • AVLTree AVL平衡树
    • RedBlackTree 红黑树
    • SkipList 跳跃表
    • BPlusTree B+树
    • BMinusTree B-树
  • Chapter-5 DynamicProgramming 第5章 动态规划
    • Section-1 LinearDP 第1节 线性动规
      • LongestCommonSubsequence 最长公共子序列
      • LongestIncreasingSubsequence 最长递增子序列
      • BidirectionalSubsequence 双向子序列
      • MaximumContinuousSubsequenceSum 最大连续子序列和
      • LongestPalindromicSubsequence 最长回文子序列
    • Section-2 BagDP 第2节 背包问题
      • 01-Bag 01背包
      • CompleteBag 完全背包
      • TwoDimensionBag 二维背包
    • Section-3 RegionalDP 第3节 区域动规
      • MinimumMergeCost - 最小合并代价
      • UniquePath 唯一路径
      • TrianglePath 三角形路径
    • Section-4 TreeDP 第4节 树形动规
      • MaximumBinaryTree 最大二叉树
      • MaxMultipleTree 最大多叉树
      • MaximumBinaryTreeRadiusSum 最大二叉树和
  • Chapter-6 GraphTheory 第6章 图论
    • Section-1 Traverse 第1节 遍历
      • DepthFirstSearch 深度优先搜索
      • BreadthFirstSearch 广度优先搜索
      • TopologicalSort 拓扑排序
      • EulerCycle 欧拉回路
    • Section-2 MinSpanningTree 第2节 最小生成树
      • Kruskal Kruskal算法
      • Prim Prim算法
    • Section-3 ShortestPath 第3节 最短路径
      • BellmanFord BellmanFord算法
      • Dijkstra Dijkstra算法
      • FloydWarshall FloydWarshall算法
      • DifferentConstraints 差分约束
    • Section-4 StronglyConnectedComponents 第4节 强连通分支
      • Kosaraju Kosaraju算法
      • Tarjan Tarjan算法
      • 2-SAT 2-SAT问题
    • Section-5 NetworkFlow 第5节 网络流
      • EdmondsKarp EdmondsKarp算法(最短路径增广算法)
      • PushRelabel 压入与重标记算法
      • Dinic - Dinic算法
      • MinimumCostFlow - 最小费用流
      • MultipleSourceMultipleSinkMaxflow - 多源点多汇点最大流
    • Section-6 BinaryMatch 第6节 二分匹配
      • Hungarian 匈牙利算法
      • HopcroftKarp Hopcroft-Karp算法
      • MatchToMaxflow 二分匹配转化为最大流
      • KuhnMunkres Kuhn-Munkres算法
      • Introduction-Domination,Independent,Covering,Clique 介绍支配集、独立集、覆盖集和团
      • WeightedCoveringAndIndependentSet 最小点权覆盖和最大点权独立集
      • MinimumDisjointPathCovering 最小不相交路径覆盖
      • MinimumJointPathCovering 最小可相交路径覆盖
      • Coloring 染色问题
  • Chapter-7 CombinatorialMathematics 第7章 组合数学
    • FullPermutation 全排列
    • Combination 组合
    • Permutation 排列
    • PermutationGroup 置换群
  • Chapter-8 NumberTheory 第8章 数论
    • PrimeSieve 素数筛法
    • GreatestCommonDivisor 最大公约数
    • Euclid 欧几里得算法
    • ExtendedEuclid 扩展欧几里得算法
    • ChineseRemainerTheorem 中国剩余定理
    • ModularExponentiation 模幂运算
  • Chapter-9 LinearAlgebra 第9章 线性代数
    • Section-1 Matrix 第1节 矩阵
      • Strassen Strassen算法
      • GaussElimination 高斯消元法
      • LUP LUP分解
      • InverseMatrix 矩阵求逆
    • Section-2 LinearProgramming 第2节 线性规划
      • Simplex 单纯形算法
      • Dinkelback Dinkelback算法
  • Chapter-10 AnalyticGeometry 第10章 解析几何
    • Section-1 Polygon 第1节 多边形
      • Cross 向量叉积
      • SegmentIntersection 线段相交
      • Sweeping 扫除算法
      • ConvexPolygonArea 凸多边形面积
      • ConvexPolygonGravityCenter 凸多边形重心
      • NearestNeighbor 最近点对
    • Section-2 ConvexHull 第2节 凸包
      • GrahamScan Graham扫描算法
      • QuickHull 快速凸包算法
      • RotatingCalipers 旋转卡壳
  • Chapter-11 PatternMatch 第11章 文本匹配
    • SimpleMatch 简单匹配
    • AhoCorasickAutomata AC自动机
    • KnuthMorrisPratt KMP匹配算法
    • RabinKarp RabinKarp算法
    • BoyerMoore BoyerMoore算法
  • Chapter-12 GameTheory 第12章 博弈论
    • BashGame 巴什博弈
    • WythoffGame 威佐夫博弈
    • NimGame 尼姆博弈
Powered by GitBook
On this page
  • 简介
  • 渐进记号
  • 复杂度
  • Introduction to Algorithms
  1. Chapter-1 BasicKnowledge 第1章 基础知识

TimeComplexity 时间复杂度

PreviousChapter-1 BasicKnowledge 第1章 基础知识NextRecursion 递归式

Last updated 6 years ago

简介

狭义的说,算法是利用计算机软件解决数学问题的方法。对于具有确定数学模型的问题,将问题数据输入算法中就可以得到该问题的解。简单的问题比如求两个位于[1000000000,−1000000000][1000000000, -1000000000][1000000000,−1000000000]之间的整数之和,这个问题的输入数据是两个整数aaa和bbb,解是整数ccc,其中c=a+bc = a + bc=a+b。复杂的问题比如求拥有nnn个节点网络流的最大流,输入数据是一个网络流G=<V,E>G = <V, E>G=<V,E>,解是该网络流的最大流FmaxF_{max}Fmax​。

时间复杂度是衡量算法性能的度量。如果把算法比作数学中的函数,那么时间复杂度就是运行该函数所消耗的时间、空间(内存)。一般将简单的数学计算、读写变量看作基本操作,其消耗的时间看作基本时间单位。基本操作只是一种抽象的认知,并不是死板规定。比如在计算两个32位整数a×ba \times ba×b的问题上,考虑下面两种算法:

(1) 累加模拟法:重复aaa个bbb累加,或bbb个aaa累加。该算法把一次相加看作一个基本操作,则其所需时间至多为max(a,b)max(a, b)max(a,b)个时间单位;

(2) :利用位操作计算两整数相乘。假设a=b=10000a = b = 10000a=b=10000,那么第(1)(1)(1)种算法需要100001000010000次累加操作,而该算法只需要52=255^2 = 2552=25次位操作,而且CPU的位操作速度极快,一次位操作所需的真正时间远小于一次整数加法操作;

在上面两种算法中,认为加法操作是第(1)(1)(1)个算法中的基本操作,位操作是第(2)(2)(2)个算法中的基本操作。虽然实际的x86或amd64架构CPU上加法操作和位操作的性能相差甚远,但在算法中都抽象的认为它们都是基本操作,忽略其细节的差别。我们更关注第(2)(2)(2)个算法通过利用整数a=b=10000a = b = 10000a=b=10000的比特位为555,远小于整数本身100001000010000,从而将运算次数从100001000010000次降低到了525^252次带来的提高。

渐进记号

不同问题的数据规模是不一样的,求两整数之和的问题规模是两个整数,即222;求拥有nnn个节点的网络流的最大流的问题规模则是nnn。常用渐进记号TTT表示一个问题的规模,比如T(1)T(1)T(1)表示问题规模是常数的,T(n)T(n)T(n)表示问题规模是线性的。

不同算法消耗的时间、空间也不一样,用渐进记号OOO来描述算法的时间复杂度或空间复杂度。常见的时间复杂度有:

(1) 常数时间:O(1)O(1)O(1),不论问题规模,算法都能在一个固定时间内解决问题,这里的111并非特指1次操作,而是指常数数量操作,因此也不存在O(2),O(10)O(2), O(10)O(2),O(10)这样的复杂度。比如上文中的两整数相加;

(2) 对数时间:O(log2n)O(log_2 n)O(log2​n)、O(n⋅log2n),对于数据规模为O(n \cdot log_2 n),对于数据规模为O(n⋅log2​n),对于数据规模为 n $$的问题,可以在对数时间内解决。比如;

(3) 线性时间:O(n)O(n)O(n),对于数据规模为nnn的问题,解决时间随着数据规模的增长呈线性增长;

(4) 二次方时间:O(n2)O(n^2)O(n2),对于数据规模为nnn的问题,需要在次方级别的时间解决。比如图论中遍历一个拥有nnn个节点完全图的所有边,需要嵌套的内外两层循环来遍历图中的所有节点,外层遍历图中的每个节点,内层对于每个节点又需要遍历图中的其他所有节点;

(5) 三次方时间O(n3)O(n^3)O(n3)、阶乘时间O(n!)O(n!)O(n!)等等;

算法复杂度的关键在于计算模型所消耗的操作数量,随着问题规模增长的膨胀程度。当问题规模nnn足够大时有:

O(n3)>O(n2)>O(n⋅log2n)>O(n)>O(log2n)>O(1)O(n^3) \gt O(n^2) \gt O(n \cdot log_2 n) \gt O(n) \gt O(log_2 n) \gt O(1)O(n3)>O(n2)>O(n⋅log2​n)>O(n)>O(log2​n)>O(1)

渐近记号给出了一个函数的上界和下界。

复杂度

判定一个算法的时间复杂度或空间复杂度需要一定的推导过程(非常熟悉的也可以一眼看出来)。

算法步骤可以转化为等式,等式左右两边分别是计算后和计算前的问题规模。转化等式遵循以下几个原则:

(1) 用常数复杂度O(1)O(1)O(1)代替运算中的所有基本操作。比如z=a+b×c÷(2∗d+e)z = a + b \times c \div (2 * d + e)z=a+b×c÷(2∗d+e)的复杂度为O(1)O(1)O(1);

(2) 在函数中只保留最高阶运算,删除低阶运算。比如n2+log2n+3×4n^2 + log_2 n + 3 \times 4n2+log2​n+3×4的复杂度为O(n2)+O(log2n)+O(1)O(n^2) + O(log_2 n) + O(1)O(n2)+O(log2​n)+O(1),删除低阶运算后复杂度为O(n2)O(n^2)O(n2);

(3) 如果运算的复杂度高于O(1)O(1)O(1),则将周围的常数乘数去掉。比如2⋅n2 \cdot n2⋅n的复杂度为O(2⋅n)O(2 \cdot n)O(2⋅n),将常数乘数去掉后复杂度为O(n)O(n)O(n);

下面我们对几个算法的时间复杂度进行推导:

(1) 两整数相加c=a+bc = a + bc=a+b

T(1)=T(1)+T(1)=O(1)T(1) = T(1) + T(1) = O(1)T(1)=T(1)+T(1)=O(1)

上式中,等号左边是计算后的结果,其规模为T(1)T(1)T(1)(结果为一个整数);等号右边是计算前的问题规模,加法操作的时间复杂度为O(1)O(1)O(1),因此该算法的时间复杂度为O(1)O(1)O(1)。

(2) 对拥有nnn个互不相等的整数的数组进行快速排序

T(n)={1n=12⋅T(n2)+O(n)n>1T(n) = \begin{cases} 1 & n = 1 \\ 2 \cdot T(\frac{n}{2}) + O(n) & n \gt 1 \end{cases}T(n)={12⋅T(2n​)+O(n)​n=1n>1​

快速排序的每次递归中,首先需要选取一个元素作为哨兵,然后遍历所有元素,将小于哨兵的元素移动到其左边,将大于哨兵的元素移动到其右边,该遍历操作的时间复杂度为O(n)O(n)O(n)。之后对于哨兵左右两边的子数组,递归的进行下一轮移动操作。因此可以得到上式,等号左边是本次操作前的问题规模T(n)T(n)T(n),等号右边是本次操作后还需要解决的问题规模,即2个T(n2)T(\frac{n}{2})T(2n​),而本次操作所需要的操作代价为O(n)O(n)O(n)。

对该递归式推导可得:

T(n)=2⋅T(n2)+n=2⋅T(2⋅T(n22)+n2)+n=22⋅T(n22)+2⋅n=2⋅T(2⋅T(n23)+n22)+2⋅n=23⋅T(n23)+3⋅n=⋯\begin{matrix} T(n) & = & 2 \cdot T(\frac{n}{2}) + n & & \\ & = & 2 \cdot T(2 \cdot T(\frac{n}{2^2}) + \frac{n}{2}) + n & = & 2^2 \cdot T(\frac{n}{2^2}) + 2 \cdot n \\ & = & 2 \cdot T(2 \cdot T(\frac{n}{2^3}) + \frac{n}{2^2}) + 2 \cdot n & = & 2^3 \cdot T(\frac{n}{2^3}) + 3 \cdot n \\ & = & \cdots & & \end{matrix}T(n)​====​2⋅T(2n​)+n2⋅T(2⋅T(22n​)+2n​)+n2⋅T(2⋅T(23n​)+22n​)+2⋅n⋯​==​22⋅T(22n​)+2⋅n23⋅T(23n​)+3⋅n​

假设递归层数为LLL,可得:

T(n2L)=1T(\frac{n}{2^L}) = 1T(2Ln​)=1

因为:

n2L=1\frac{n}{2^L} = 12Ln​=1

可以得到:

L=log2nL = log_2 nL=log2​n

因此递归式可推导为:

T(n)=2L⋅T(n2L)+L⋅n=2log2n+n⋅log2n=n+n⋅log2n=O(n⋅log2n)\begin{matrix} T(n) & = & 2^L \cdot T(\frac{n}{2^L}) + L \cdot n \\ & = & 2^{log_2 n} + n \cdot log_2 n \\ & = & n + n \cdot log_2 n \\ & = & O(n \cdot log_2 n) \end{matrix}T(n)​====​2L⋅T(2Ln​)+L⋅n2log2​n+n⋅log2​nn+n⋅log2​nO(n⋅log2​n)​

最终可以得到快速排序的时间复杂度为O(n⋅log2n)O(n \cdot log_2 n)O(n⋅log2​n)。

Introduction to Algorithms

Booth’s Multiplication Algorithm
二分搜索(Binary Search)
I.Foundations - 2.Getting Started - 2.3.Designing algorithms