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

Algorithm

PreviousComputer OrganizationNextComplexity

Last updated 5 years ago

Was this helpful?

数据结构是指一组数据的存储结构,如队列、栈、堆,算法是操作数据的一组方法,如二分查找、动态规划。

数据结构与算法是相辅相成的,数据结构是为算法服务的,算法需要作用在特定的数据结构上。比如数组具有随机访问的特点,二分查找需要用数组来存储数据,若用链表,二分查找就无法工作了。

十个重要的数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树。

十个重要的算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

对于数据结构和算法,不只是要了解它是什么,更重要的是要知道:它的来历、特点、解决的问题、应用场景。

    • 并查集

  • 算法思想:

四种算法思想比较:

  • 分治算法解决的问题大部分都不能抽象成多阶段决策问题;贪心、回溯、动态规划解决的问题都可以抽象成多阶段决策。

  • 回溯算法是“万金油”,能用动态规划、贪心解决的问题,基本都能用回溯解决,回溯相当于穷举,时间复杂度非常高。

  • 动态规划能解决的问题需要满足最优子结构、无后效性、重复子问题三个特性;动态规划高效的原因就是回溯算法中有大量重复子问题,而分治算法相反,要求子问题不能重复。

  • 贪心算法本质是动态规划的一种特殊情况,解决问题需要满足最优子结构、无后效性、贪心选择性,不用强调重复子问题。贪心选择性的意思是通过局部的最优选择,能产生全局的最优选择。

复杂度分析
线性表结构
排序
查找
跳表
哈希表
Tree
图
字符串匹配算法
布隆过滤器
贪心算法
分治算法
回溯算法
动态规划
时间复杂度
空间复杂度
Array
List
Stack
Queue
二叉查找树
平衡二叉查找树
红黑树
递归树
堆
B 树
B+ 树