Notes
  • Introduce
  • Go
    • Grammar
      • Basic
      • Goroutines & Channels
      • Test
    • System Library
      • Module
      • sync
      • context
      • net
    • Concurrency in Go
    • The Go Memory Model
    • Code Snippet
  • Rust
    • The Rust Programming Language
    • Rust by Example
  • JAVA
    • Preface
    • Grammar
      • Basic
      • Data Types
      • Operator
      • Exceptions
    • Class Libraries
      • Collection
      • Stream
      • IO
      • NIO
      • RMI
    • Concurrency
      • Preface
      • JMM
      • Synchronized & CAS
      • Deadlock
      • Thread
      • Lock & Condition
      • Utility Class
      • Thread-safe Collection
      • Atomic Class
      • Fork/Join
      • Concurrency Design Patterns
        • Immutable
        • Copy-on-Write
        • ThreadLocal
        • Multitheading If
        • Division
    • JVM
      • Class & Instance Initialization
      • Runtime Data Area
      • Garbage Collection
    • Web Container
      • Tomcat Architecture
      • Jetty Architecture
    • Spring
    • Tuning
      • Programming
  • Computer Science
    • Computer Organization
    • Algorithm
      • Complexity
      • Linear List
      • Sort
      • Binary Search
      • Skip List
      • Hash Table
      • Tree
      • Graph
      • String Matching
      • Bloom Filter
      • Greedy Algorithm
      • Divide and Conquer
      • Back Tracking
      • Dynamic Programming
    • Network Protocol
      • Pysical Layer
      • Data Link Layer
      • Network Layer
      • Transport Layer
      • Application layer
      • HTTP
      • HTTP/2 in Action
    • Operating System
      • Basic
      • System Initialization
      • Diagnostic Tools
      • CPU Diagnosis
      • Memory Diagnosis
      • Disk Diagnosis
      • Network Diagnosis
      • Monitor System
    • Design Patterns
      • UML
      • OOP
      • Principle
      • Refactoring & Specification
      • Creational
        • Singleton
        • Factory
        • Builder
        • Prototype
      • Structural
        • Proxy
        • Bridge
        • Decorator
        • Adapter
        • Facade
        • Composite
        • FlyWeight
      • Behavioral
        • Observer
        • Template Method
        • Strategy
        • State
        • Iterator
        • Chain of Responsibility
    • Distributed System
      • Protocol & Algorithm
      • Transcation
      • Theory
      • Resource Management
      • Scheduling
      • Computing
      • Message Queue
      • Cache
      • Consistent Hashing
  • database
    • InfluxDB
      • In-Memory Index
      • Meta
    • MySQL
      • SQL
      • Architecture
      • Log
      • Transaction
      • Indexing
      • Lock
      • Storage
    • Redis
    • Elasticsearch
      • Local Debug
    • HBase
    • Kafka
    • ZooKeeper
  • Reading
    • RocketMQ
    • 演说之禅
    • So Good They Can't Ignore You
    • 学会提问
    • Lecture
  • Other
    • v2ray
    • Kubernetes
    • Git
    • Maven
    • Anaconda And Conda
    • Fuck! Shit!
      • Remove Final by Reflection
      • Ingress Host
      • ExecuterService submit
  • Open source contribution
Powered by GitBook
On this page
  • 时间复杂度
  • 空间复杂度

Was this helpful?

  1. Computer Science
  2. Algorithm

Complexity

时间复杂度

代码的执行总时间T(n)与所有行代码的执行总次数f(n)成正比,即:

T(n) = O(f(n))

n 表示数据规模大小,O 表示正比例函数。

大 O 时间负复杂度并不代表代码真正执行时间,而是表示代码执行时间随数据规模增长的变化趋势,也叫渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

当n很大时,f(n)中的低阶、常量、系数并不影响增长趋势,所以可以忽略,如O(2n^2+2n+3)可表示为O(n^2)。所以时间复杂度分析有一些实用技巧:

  1. 只关注循环次数最多的一行代码。

  2. 加法法则,总复杂度等于量级最大的复杂度。如,有两段先后执行的代码复杂度分别为O(n)与O(n^2),那么总的复杂度为O(n^2)。

  3. 乘法法则,嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。如,有两段嵌套的代码复杂度分别为O(n)与O(n^2),那么总的复杂度为O(n^3)。

几种常见的时间复杂度:

# 多项式量级
O(1) //常量阶
O(logn) //对数阶
O(n) //线性阶
O(nlogn) //线性对数阶,如归并排序、快速排序
O(n^2) //平方阶
O(n^3) //立方阶
O(n^k) //k次方阶
​
# 非多项式量级
O(2^n) //指数阶
O(n!) //阶乘阶

我们把非多项式量级的算法问题称为 NP 问题(Non-Deterministic Polynomial)。

当一段代码的复杂度由两个数据规模来决定,并且不知道两个数据规模量级谁的大,那么复杂度对加法规则是: O(f(m) + f(n)) ,乘法规则是:O(f(m) * f(n)) 。

不同情况下的复杂度

  • 最好情况时间复杂度(best case time complexity)

  • 最坏情况时间复杂度(worst case time complexity)

  • 平均情况时间复杂度(average case time complexity)

同一代码块在不同情况下,时间复杂度有量级差距,我们就需要使用上述三种复杂度表示。比如下面代码,在数组中查找数据,最好 O(1),最坏 O(n),平均 O(n)。

int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

摊还分析

对一个数据结构进行连续操作,大部分情况时间复杂度很低,只有个别情况时间复杂度很高,而且这些操作之间存在前后关系,这时,可以将这组操作一起分析,看能否把时间复杂度较高的操作平摊到其它时间复杂度较低的操作。摊还分析得到的时间复杂度为均摊时间复杂度(amortized time complexity)。

本质上均摊时间复杂度是一种特殊的平均时间复杂度,一般两者相等。

空间复杂度

渐进空间复杂度(asymptotic space complexity)表示算法的存储空间与数据规模之间的增长关系。

常用空间复杂度:O(1)、O(n)、O(n^2)。

PreviousAlgorithmNextLinear List

Last updated 5 years ago

Was this helpful?