This website requires JavaScript.

数据结构与算法(更新中)

2018.03.20 21:40字数 10584阅读 688喜欢 20评论 0

时间复杂度与空间复杂度

时间复杂度

  • 时间频度: 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才知道。一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行的次数多,它花费时间就多。一个算法中语句执行次数称为语句频度或时间频度,记为 T(n)。
  • 时间复杂度:在时间频度中,n 称为问题的规模,当 n 不断变化时,时间频度 T(n) 也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。一般情况下,算法中基本操作重复执行的次数是问题规模 n 的某个函数,用 T(n) 表示,若有某个辅助函数 f(n),使得当 n 趋近于无穷大时,T(n)/f(n) 的极限值为不等于0的常数,则称 f(n) 是 T(n) 的同数量级函数。记做 T(n) = O(f(n)),称 O(f(n)) 为算法的渐近时间复杂度,简称时间复杂度。

    在时间频度不相同时(T(n) 不同),时间复杂度有可能相同,如 T(n) = n2 + 3n + 4 与 T(n) = 4n2 + 2n + 1 它们的频度不同,但时间复杂度相同,都为 O(n2)

    常见的时间复杂度有:常数阶O(1), 对数阶 O(log2n),线性阶 O(n),线性对数阶 O(nlog2n),平方阶 O(n2),立方阶 O(n3),......,k 次方阶 O(nk),指数阶 O(2n),随着问题规模 n 不断增大,上述时间复杂度不断增大,算法的执行效率降低。

空间复杂度

空间复杂度:与时间复杂度类似,一个算法的空间复杂度 S(n) 定义为该算法所耗费的存储空间。包括以下两部分:

  • 固定部分。这部分空间大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。
  • 可变空间。这部分空间主要包括动态分配的空间,以及递归栈所需的空间等。这部分的空间大小与算法有关。

栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾,称做栈顶,另一端叫做栈底。
在栈里,新元素都靠近栈顶,旧元素都靠近栈底。

TypeScript 实现:

class Stack {
  item: number[]
  constructor () {
    this.item = []
  }

  // 添加元素
  push (e: number): void {
    this.item.push(e)
  }

  // 移出
  pop (): void {
    this.item.pop()
  }

  // 返回栈顶元素
  peek (): void {
    this.item[this.item.length - 1]
  }

  // 是否为空
  isEmpty (): boolean {
    return !this.item.length
  }

  // 清空栈
  clear (): void {
    this.item = []
  }
}

使用栈

const stack = new Stack()
stack.push(1)
stack.push(10)

stack.peek()
stack.isEmpty()

队列

队列与栈相反,遵循先进先出(FIFO)的原则的一组有序的项,队列从尾部添加新元素,并从顶部移除元素,最后添加的元素必须排列在队列的末尾。

TypeScript 实现

class Queue {
  item: number[]
  constructor () {
    this.item = []
  }

  // 进入队列
  push (n): void {
    this.item.push(n)
  }

  // 移除队列
  dequeue (): void {
    this.item.shift()
  }

  // 是否为空
  isEmpty (): boolean {
    return !this.item.length
  }

  // 清空
  clear (): void {
    this.item = []
  }
}

const queue = new Queue()

queue.push(1)
queue.push(2)

queue.dequeue()

queue.isEmpty()

queue.clear()

优先队列

优先队列是队列数据结构的另一种表现,其主要是指队列元素的添加和移除是基于优先级的,现实生活中也比较常见,例如高铁的一等座,便不需要排队到二等座人群中。

实现优先队列有两种选择,可以设置队列的优先级,然后在对应位置添加元素;或者用入队操作添加元素,然后按照优先级移除他们。

示例代码如下:

interface Item {
  name: string
  priority: number
}

class Queue {
  item: Item[]
  constructor () {
    this.item = []
  }

  enqueue (name: string, priority: number): void {
    let queueEl = { name, priority }
    if (this.isEmpty()) {
      this.item.push(queueEl)
    } else {
      const Ind = this.item.findIndex(n => n.priority === queueEl.priority)
      if (Ind > -1) this.item.splice(Ind, 0, queueEl)
      else this.item.push(queueEl)
    }
  }

  isEmpty (): boolean {
    return !this.item.length
  }

  // others
}

链表

队列和栈都是顺序存储结构,最大的缺点是改变了其中一个元素的排列时,都会引起整个合集的变化,其原因是在内存中的存储本来就是连贯没有间隙的,删除一个自然就要补上。

链式储存结构与顺序储存结构不同,链式结构不关心数据的排列,只需要在每一个元素的内部把下一个数据的位置记录即可。

在链式结构中:数据 = 信息 + 地址。链表就是一组即诶单组成的合集。每一个节点都有一个数据块引用指向它的下一个节点。

优势比较明显,插入一个数据不需要关系其排列情况,只要把“链”的指向衔接上。

单向链表

单向链表,是链表中最简单的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。

typescript 实现:

interface NodeInterface<T> {
  tag: T
  next?: NodeInterface<T>
}

// 每个节点
class NodeTm<T> implements NodeInterface<T> {
  tag: T
  next?: NodeInterface<T>
  constructor (tag: T) {
    this.tag = tag
  }
}

// 链表 interface
interface LinkNodesInterface<T> {
  // head
  headNode?: NodeInterface<T>

  // 添加元素
  appendNode (tag: T): void

  // 任意位置添加节点
  insertNode (targetTag: T, tag: T): void

  // 删除元素
  removeNode (tag: T) : NodeInterface<T>

  findNode (tag: T): NodeInterface<T>
}

class LinkNodes<T> implements LinkNodesInterface<T> {
  headNode: NodeInterface<T>

  constructor (tag: T) {
    this.headNode = new NodeTm<T>(tag)
  }

  appendNode (tag: T): void {
    const node = new NodeTm<T>(tag)
    let currentNode = this.headNode
    while (currentNode.next) {
      currentNode = currentNode.next
    }
    currentNode.next = node
  }

  insertNode (targetTag: T, tag: T) {
    const node = new NodeTm<T>(tag)
    let currentNode = this.headNode
    while (currentNode.tag !== targetTag && currentNode.next) {
      currentNode = currentNode.next
    }
    node.next = currentNode.next
    currentNode.next = node
  }

  removeNode (tag: T) {
    // 需要找到上一节点
    let prevNode = this.headNode
    while (prevNode.next && prevNode.next.tag !== tag) {
      prevNode = prevNode.next
    }
    if (prevNode.next) prevNode.next = prevNode.next.next
    return {
      tag,
      next: prevNode.next
    }
  }

  findNode (tag: T) {
    let currentNode = this.headNode
    while (currentNode.tag !== tag && currentNode.next) {
      currentNode = currentNode.next
    }
    return currentNode
  }
}

const linkList = new LinkNodes<number>(0)

linkList.appendNode(1)
linkList.appendNode(3)
linkList.insertNode(1, 2)
console.log(linkList.findNode(1))
console.log('==========')
console.log(linkList.removeNode(2))
console.log('==========')
console.log(linkList.findNode(1))

双向链表

在双向链表里,每个节点有三个值:数值、向后的节点链接、向前的节点链接。

实现大部分和单向列表相同:


interface NodeInterface<T> {
  tag: T
  next?: NodeInterface<T>
  prev?: NodeInterface<T>
}

// 每个节点
class NodeTm<T> implements NodeInterface<T> {
  tag: T
  next?: NodeInterface<T>
  prev?: NodeInterface<T>
  constructor (tag: T) {
    this.tag = tag
  }
}

// 链表 interface
interface LinkNodesInterface<T> {
  // head
  headNode?: NodeInterface<T>

  // 添加元素
  appendNode (tag: T): void

  // 任意位置添加节点
  insertNode (targetTag: T, tag: T): void

  // 删除元素
  removeNode (tag: T) : NodeInterface<T>

  findNode (tag: T): NodeInterface<T>
}

class LinkNodes<T> implements LinkNodesInterface<T> {
  headNode: NodeInterface<T>

  constructor (tag: T) {
    this.headNode = new NodeTm<T>(tag)
  }

  appendNode (tag: T): void {
    const node = new NodeTm<T>(tag)
    let currentNode = this.headNode
    while (currentNode.next) {
      currentNode = currentNode.next
    }

    currentNode.next = node
    node.prev = currentNode
  }

  insertNode (targetTag: T, tag: T) {
    const node = new NodeTm<T>(tag)
    let currentNode = this.findNode(targetTag)
    node.next = currentNode.next
    node.prev = currentNode
    currentNode.next = node
  }

  removeNode (tag: T) {
    let currentNode = this.headNode
    while (currentNode.tag !== tag && currentNode.next) {
      currentNode = currentNode.next
    }
    if (currentNode.prev) {
      currentNode.prev.next = currentNode.next
      currentNode.next.prev = currentNode.prev
    }
    return {
      tag,
      next: currentNode.next,
      prev: currentNode.prev
    }
  }

  findNode (tag: T) {
    let currentNode = this.headNode
    while (currentNode.tag !== tag && currentNode.next) {
      currentNode = currentNode.next
    }
    return currentNode
  }
}

const linkList = new LinkNodes<number>(0)

linkList.appendNode(1)
linkList.appendNode(3)
linkList.insertNode(1, 2)
console.log(linkList.findNode(1))
console.log('==========')
console.log(linkList.removeNode(2))
console.log('==========')
console.log(linkList.findNode(1))

相比于单向链表,双向链表更适用于大量数据插入、删除。

栈和队列查找元素时比较快,插入和删除则比较慢(改变其中一个元素的排列时,会引起整个集合的变化)。
链表查找元素时比较慢(需要从 head 开始向下查找),插入和删除比较快。

数是一种抽象数据类型或是实作这种抽象数据类型的数据结构,是一种非顺序数据结构。用来模拟具有树状结构性质的数据集合。它是由 n(n > 0) 个有限节点组成一个具有层级关系的集合。

它具有一下特点:

  • 每个节点有零个或多个子节点;
  • 没有父节点的节点称为跟节点(树叶);
  • 每一个非跟节点有且只有一个父节点;
  • 除了跟节点外,每个节点可以分为多个不相交的子树;

二叉搜索树

二叉搜索树又称为二叉查找树、有序二叉树、排序二叉树,是指一颗空树,或者具有下列性质的二叉树:

  • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的跟节点的值;
  • 若任意节点的右子树不空,则右子树上所有节点的值均大于它的跟节点的值;
  • 任意节点的左、右树也分别为二叉查找树;
  • 没有健值相等的节点。

二叉搜索树相比与其他数据结构的优势在于查找、插入的时间复杂度较低。为 O(log n) 。

二叉搜索树每次插入的新的节点都是二叉查找树上新的叶子节点,在进行插入操作时,不必移动其他节点,只需改动某个节点的指针,由非空变为空即可。搜索、插入、删除的复杂度等于树高,期望 O(log n ),最坏 O(n),(数列有序,树退化成线性表)。

TypeScript 实现如下:

interface BiTreeInter {
  key: number
  left?: TreeInter
  right?: TreeInter
}

interface TreeInter {
  root: BiTreeInter
  // 搜索
  searchBST (key: number, tree?: TreeInter): boolean

  // 插入
  insertBST (key: number, tree?: TreeInter): boolean

  // 删除
  remove (key: number): void
}

class BitTree implements BiTreeInter {
  key: number
  left?: TreeInter
  right?: TreeInter
  constructor (key: number) {
    this.key = key
    this.left = null
    this.right = null
  }
}


class BSTTree implements TreeInter {

  root: BiTreeInter
  constructor (key) {
    this.root = new BitTree(key)
  }

  /**
   * 二叉搜索树 搜索
   * 若为空树,则搜索失败
   * 若 key 等于跟节点值,查找成功
   * 若 key 小于跟节点值,查找左树
   * 若 key 大于跟节点值,查找右树
   * 
   * @memberof BSTTree
   */
  searchBST (key: number, tree?: TreeInter): boolean {
    if (!tree) return false

    if (tree.root.key === key) return true
    if (tree.root.key > key) return this.searchBST(key, tree.root.right)
    if (tree.root.key < key) return this.searchBST(key, tree.root.left)
    return true
  }

  /**
   * 二叉搜索树 插入
   * 若为空树,则将节点作为跟节点插入
   * 若值等于树跟节点值,则返回失败
   * 若值小于跟节点值,则插入到左子树中
   * 若值大于跟节点值,则插入到右子树中
   * 
   * @memberof BSTTree
   */
  insertBST (key: number, tree?: TreeInter) {
    const node = new BitTree(key)
    if (!tree) tree.root = node
    else {
      if (tree.root.key === key) return false
      if (tree.root.key > key) return this.insertBST(key, tree.root.left)
      else return this.insertBST(key, tree.root.right)
    }
  }

  /**
   * 二叉搜索树 删除
   * 若节点为叶子节点,即左右子树都为空树。删除叶子节点不破坏整棵树结构,则只需修改其双亲节点的指针即可。
   * 若节点只有左子树,或者右子树时,删除节点后,只要令左子树或者右子树直接成为其双亲节点的左子树或右子树即可。
   * 若节点左右子数都存在,在删除节点之后,可以有两种做法:
   *    1、令删除节点 p 的左子树为 p 的父树 f 的左/右(依据 p 是 f 的左子树还是右子树而定)子树。 
   *       s 为 p 左子树最右下的节点,而 p 的右子树为 s 的右子树。
   *    2、令 p 的直接直接前驱(in-order predecessor)或直接后继(in-order successor)替代 p ,
   *       然后再从二叉查找树中删去它的直接前驱(或直接后继)。
   * @memberof BSTTree
   */
  remove (key: number, tree?: TreeInter) {
    if (key > tree.root.key) this.remove(key, tree.root.right)
    else if (key < tree.root.key) this.remove(key, tree.root.left)
    else this.removeBST(tree)
  }

  removeBST (tree: TreeInter) {
    if (!tree.root.left && !tree.root.right) {
      delete tree.root
    }

    // 右子为空时,重接它的左子树
    if (!tree.root.right) {
      const lChild = tree.root.left
      tree.root.key = lChild.root.key
      tree.root.left = lChild.root.left
      tree.root.right = lChild.root.right
    }

    // 左子树为空时,只需要重接它的右子树
    else if (!tree.root.left) {
      const rChild = tree.root.right
      tree.root.key = rChild.root.key
      tree.root.left = rChild.root.left
      tree.root.right = rChild.root.right
    }

    if (tree.root.right && tree.root.left) {

    }
  }
}