情不知所起,一往而深

数据结构与算法六:队列

astipsy阅读(3)

理解“队列”

队列这个概念非常好理解。你可以把它想象成排队买票,先来的先买,后来的只能站末尾。先进者先出,这就是典型的“队列”

我们知道,栈只支持两个基本操作:入栈push()和出栈pop()。队列跟栈非常相似,支持的操作也很有限,最基本的操作也是两个:入队enqueue(),放一个数据到队列尾部;出队dequeue(),从队列头部取一个元素。

image

所以,队列跟栈一样,也是一种操作受限的线性表数据结构

队列的概念很好理解,基本操作也很容易掌握。作为一种非常基础的数据结构,队列的应用也是非常广泛的,特别是一些具有某些额外特性的队列,比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中,起着关键性的作用。比如高性能队列Disruptor、Linux环形缓存,都用到了循环并发队列;Java concurrent 并发包利用ArrayBlockingQueue来实现公平锁等。

顺序队列和链式队列

我们知道了,队列跟栈一样,也是一种抽象的数据结构。它具有先进先出的特性,支持在队尾插入元素,在队头删除元素。

跟栈一样,队列可以用数组来实现,也可以用链表来实现。用数组实现的栈叫做顺序栈,用链表实现的栈叫做链式栈。同样,用数组实现的队列叫做顺序队列,用链表实现的队列叫做链式队列

下面是基于数组的实现方法。

// 用数组实现的队列
public class ArrayQueue {
  // 数组:items,数组大小:n
  private String[] items;
  private int n = 0;
  // head表示队头下标,tail表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为capacity的数组
  public ArrayQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 如果tail == n 表示队列已经满了
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果head == tail 表示队列为空
    if (head == tail) return null;
    // 为了让其他语言的同学看的更加明确,把--操作放到单独一行来写了
    String ret = items[head];
    ++head;
    return ret;
  }
}

比起栈的数组实现,队列的数组实现稍微有点复杂。

对于栈来手,我们只需要一个栈顶指针就可以了。但是队列需要两个指针:一个是head指针,指向队头;一个是tail指针,指向队尾。

可以结合下面这幅图来理解。当a、b、c、d依次入队之后,队列中的head指针指向下标为0的位置,tail指针指向下标为4的位置。

image

当我们调用两次出队操作之后,队列中的head指针指向下标为2的位置,tail指针仍然指向下标为4的位置。

image

随着不停的出队、入队操作,head和tail都会持续往后移动。当tail移动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据了。

在数组那一节中,我们也遇到过类似的问题,采用的方法是数据搬移。但是,每次进行出队操作都相当于删除数组下标为0的数据,要搬移整个队列中的数据,这样出队操作的时间复杂度就会从原来的O(1)变为O(n)。

实际上,我们在出队时可以不用搬移数据。如果没有空闲空间了,我们只需要在入队时,再集中触发一次数据的搬移操作。借助这个思想,出队函数dequeue()保持不变,我们稍加该遭一下入队函数enqueue()的实现,就可以轻松解决刚才的问题了。

   // 入队操作,将item放入队尾
  public boolean enqueue(String item) {
    // tail == n表示队列末尾没有空间了
    if (tail == n) {
      // tail ==n && head==0,表示整个队列都占满了
      if (head == 0) return false;
      // 数据搬移
      for (int i = head; i < tail; ++i) {
        items[i-head] = items[i];
      }
      // 搬移完之后重新更新head和tail
      tail -= head;
      head = 0;
    }

    items[tail] = item;
    ++tail;
    return true;
  }

从代码中我们看到,当队列的tail指针移动到数组的最右边后如果有新的数据入队,我们可以将head到tail之间的数据,整体搬移到数组中0到tail-head的位置。

image

接下来,我们再来看下基于链表的队列实现方法

基于链表的实现,我们同样需要两个指针:head指针和tail指针。它们分别指向链表的第一个结点和最后一个结点。如图,入队时,tail->next = new_node,tail = tail->next;出队时,head = head->next。

image

循环队列

我们刚才用数组来实现队列的时候,在tail==n时,会有数据搬移操作,这样入队操作性能就会收到影响。那有没有办法能够避免数据搬移呢?我们来看看循环队列的解决思路。

循环队列,顾名思义,它长得像一个环。原本数组是有头有尾的,是一条直线。现在我们把首尾相连,扮成一个环。

image

我们可以看到,图中这个队列的大小为8,当前head=4,tail=7。当有一个新的元素a入队时,我们放入下标为7的位置。但这个时候,我们并不把tail更新为8,而是将其在环中后移一位,到下标为0的位置。当再有一个元素b入队时,我们将b放入下标为0的位置,然后tail加1更新为1.所以,在a,b依次入队之后,循环队列中的元素就变成了下面的样子:

image

通过这样的方法,我们成功避免了数据搬移操作。看起来不难理解,但是循环队列的代码实现难度要比前面讲的非循环队列难多了。要想写出没有bug的循环队列的实现代码,最关键的是,确定好空队和队满的判定条件

在用数组实现的非循环队列中,队满的判断条件是tail==n,队空的判断条件是head==tail。

队列为空的判断条件依然是head==tail,但队列满的判断条件就稍微有点复杂了。

image

就像图中的队满的情况,tail=3,head=4,n=8,所以总结一下规律就是:(3+1)%8=4。多画几张队满的图,你就会发现,当队满时,(tail+1)%n=head

你有没有发现,当队列满时,图中的tail指向的位置实际上是没有存储数据的。所以,循环队列会浪费一个数组的存储空间。

public class CircularQueue {
  // 数组:items,数组大小:n
  private String[] items;
  private int n = 0;
  // head表示队头下标,tail表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为capacity的数组
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 队列满了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果head == tail 表示队列为空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
}

阻塞队列和并发队列

阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说,就是在队列为空的时候,从队头取数据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。

image

你应该已经发现了,上述定义就是一个“生产者 - 消费者模型”!是的,我们可以使用阻塞队列,轻松实现一个“生产者 - 消费者模型”!

这种基于阻塞队列实现的“生产者 - 消费者模型”,可以有效的协调生产和消费的速度。当“生产者”生产数据的速度过快,“消费者”来不及消费时,存储数据的队列很快就会满了。这个时候,生产者就会阻塞等待,知道“消费者”消费了数据,“生产者”才会被唤醒继续“生产”。

而且不仅如此,基于阻塞队列,我们还可以通过协调“生产者”和“消费者”的个数,来提高数据的处理效率。比如前面的例子,我们可以多配置几个“消费者”,来应对一个“生产者”。

image

阻塞队列,在多线程的情况下,会有多个线程同时操作队列,这个时候就会存在线程的安全问题。

线程安全的队列我们叫做并发队列。最简单直接的实现方式是直接在enqueue()、dequeue()方法上加锁,但是锁粒度大并发度会比较低,同一时刻仅允许一个存或者取操作。实际上,基于数组的循环队列,利用CAS原子操作,可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

线程池没有空闲线程时,新的任务请求时如何处理?

我们一般有两种处理策略。第一种就是非阻塞的处理方式,直接拒绝任务请求;另一种就是阻塞的处理方式,将请求排队,等到有空闲线程时,取出排队的请求继续处理。

我们希望公平的处理每个排队请求,先进者先服务,所以队列这种数据结构很适合来存储排队请求。前面讲过,队列有基于链表和基于数组这两种实现方式。这两种实现方式对于排队请求又有什么区别呢?

基于链表的实现方式,可以实现一个支持无限排队的无界队列(unbounded queue),但是可能会导致过多的请求排队等待,请求处理的相应时间过长。所以,针对相应时间比较敏感的系统,基于链表实现的无限排队的线程池是不合适的。

而基于数组实现的有界队列(bounded queue),队列的大小是有限的,所以线程池中的队列请求超过队列大小时,接下来的请求就会被拒绝,这种方式对响应时间敏感的系统来说,就相对更加合理。不过,设置一个合理的队列大小,也是非常有讲究的。队列太大导致等待的请求太多,队列太小会导致无法充分利用系统资源,发挥最大性能。

除了前面讲到队列应用在线程池请求排队的场景之外,队列可以应用在任何有限资源池中,用于排队请求,比如数据库连接池等。实际上,对于大部分资源有限的场景,当没有空闲资源时,基本上都可以通过“队列”这种数据结构来实现请求排队

数据结构与算法五:栈

astipsy阅读(4)

理解“栈”

关于“栈”,有一个非常贴切的例子,就是一摞叠在一起的盘子。我们平时放盘子的时候,都是从下往上一个一个的放;取的时候,我们也是从上往下一个一个的依次取,不能从中间任意抽出。后进者先出,先进者后出,这就是典型的“栈”结构

image

从栈的操作特性上来看,栈是一种“操作受限”的线性表,只允许在一段插入和删除数据。

从功能上来说,数组或链表确实可以替代栈。但是,特定的数据结构是对特定场景的抽象,而且,数组或链表暴露了太多的操作接口,操作上的确灵活自由,但使用时就比较不可控,自然也就更容易出错。

当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、后进后出的特性,我们就应该首先“栈”这种数据结构。

如何实现一个“栈”?

从刚才栈的定义里,我们可以看出,栈主要包含两个操作,入栈和出栈,也就是在栈顶插入一个数据和从栈顶删除一个数据。

实际上,栈既可以用数组来实现,也可以用链表来实现。用数组实现的栈,我们叫做顺序栈,用链表实现的栈,我们叫做链式栈

下面这段代码是基于数组的顺序栈

// 基于数组实现的顺序栈
public class ArrayStack {
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           //栈的大小

  // 初始化数组,申请一个大小为n的数组空间
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // 入栈操作
  public boolean push(String item) {
    // 数组空间不够了,直接返回false,入栈失败。
    if (count == n) return false;
    // 将item放到下标为count的位置,并且count加一
    items[count] = item;
    ++count;
    return true;
  }

  // 出栈操作
  public String pop() {
    // 栈为空,则直接返回null
    if (count == 0) return null;
    // 返回下标为count-1的数组元素,并且栈中元素个数count减一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}

了解了定义和基本操作,那它的操作的时间、空间复杂度是多少呢?

不管是顺序栈和链式栈,我们存储数据只需要一个大小为n的数组就够了。在入栈和出栈的过程中,只需要一脸个临时变量存储空间,所以空间复杂度是O(1)。

注意,这里存储数据需要一个大小为n的数组,并不是说空间复杂度就是O(n)。因为,这n个空间是必须的,无法省掉。所以我们说空间复杂度的时候,是指除了原本的数据存储空间外,算法运行还需要额外的存储空间。

空间复杂度分析是不是很简单?时间复杂度也不难。不管是顺序栈还是链式栈,入栈、出栈只涉及栈顶个别数据的操作,所以时间复杂度都是O(1)。

支持动态扩容的顺序栈

刚才那个基于数组实现的栈,是一个固定大小的栈,也就是说,在初始化栈时需要事先指定栈的大小。当栈满之后,就无法再往栈里面添加数据了。尽管链式栈的大小不受限,但要存储next指针,内存消耗相对较多。

要实现一个支持动态扩容的栈,我们只需要底层依赖一个支持动态扩容的数组就可以了。当栈满了之后,我们就申请一个更大的数组,将原来的数据搬移到新数组中。

image

实际上,支持动态扩容的顺序栈,我们平时开发中并不经常用到。

对于出栈操作来说,我们不会涉及内存的重新申请和数据的搬移,所以出栈的时间复杂度仍然是O(1)。但是,对于入栈操作来说,情况就不一样了。当栈中有空闲空间时,入栈操作的时间复杂度为O(1)。但当空间不够时,就需要重新申请内存和数据搬移,所以时间复杂度就变成了O(n)。

也就是说,对于入栈操作来说,最好情况时间复杂度是O(1),最坏情况时间复杂度是O(n)。那平均情况下的时间复杂度又是多少呢?我们用摊还分析法来实战一下。

为了方便分析,我们需要事先做一些假设和定义:

  • 栈空间不够时,我们重新申请一个是原来大小两倍的数组
  • 为了简化分析,假设只有入栈操作没有出栈操作
  • 定义不设计内存搬移的入栈操作为 simple-push 操作,时间复杂度为O(1)

如果当前栈大小为K,并且已满,当再有新的数据要入栈时,就需要重新申请2倍大小的内存,并且做K个数据的搬移操作,然后再入栈。但是,接下来的K-1次入栈操作,我们都不需要再重新申请内存和搬移数据,所以这K-1次入栈操作都只需要一个simple-push操作就可以完成。

image

可以看出,这K次入栈操作,总共涉及了K个数据的搬移,以及K次simple-push操作。将K个数据搬移均摊到K次入栈操作,那每个入栈操作只需要一个数据搬移和一个simple-push操作。以此类推,入栈操作的均摊时间复杂度就为O(1)。

通过这个例子的实战分析,也印证了前面讲到的,均摊时间复杂度一般都等于最好情况时间复杂度。因为在大部分情况下,入栈操作的时间复杂度都是O(1),只有在个别情况下才会退化为O(n),所以把耗时多的入栈操作的时间均摊到其他入栈操作上,平均情况下的耗时就接近O(1)。

栈在函数调用中的应用

栈作为一个比较基础的数据结构,应用场景还是蛮多的。其中,比较经典的一个应用场景就是函数调用栈

我们知道,操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。每进入一个函数,就会将临时变量作为一个栈帧入栈,当被调用函数执行完成,返回之后,将合格函数对应的栈帧出栈。

int main() {
   int a = 1; 
   int ret = 0;
   int res = 0;
   ret = add(3, 5);
   res = a + ret;
   printf("%d", res);
   reuturn 0;
}

int add(int x, int y) {
   int sum = 0;
   sum = x + y;
   return sum;
}

从代码中可以看出,main()函数调用了add()函数,获取计算结果,并且与临时变量a想加,最后打印res的值。

image

栈在表达式求值中的应用

我们再来看栈的另一个常见的应用场景,编译器如何利用栈来实现表达式求值

为了方便解释,我将算数表达式简化为只包含加减乘除四则运算,比如:34+13*9+44-12/3。对于这个四则运算,我们人喃可以很快求解出答案,但是对于计算机来说,理解这个表达式本身就是个挺难的事儿。

实际上,编译器就是通过两个栈来实现的。其中一个保存操作数的栈,另一个是保存运算符号的栈。我们从左向右遍历表达式,当遇到数字,我们就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较。

如果运算符栈顶元素的优先级高,就将当前运算符压入栈;如果比运算符栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈的栈顶取两个操作数,然后进行计算,再把计算完的结果压入操作栈,继续比较。

下图是 3+5*8-6 的表达式

image

栈在括号匹配中的应用

除了用栈来实现表达式求值,我们还可以借助栈来检查表达式中的括号是否匹配。

我们同样简化一下背景。我们假设表达式中只包含三种括号,圆括号()、方括号[]和花括号{},并且它们可以任意嵌套。比如,{[]()},而{[}]是不合法格式。

这里也可以用栈来解决。我们用栈来保存未匹配的左括号,从左到右依次扫描字符串。当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号。如果能够匹配,比如“(”跟“)”匹配,“[”跟“]”匹配,“{”跟“}”匹配,则继续扫描剩下的字符串。如果扫描的过程中,遇到不能匹配对的右括号,或者栈中没有数据,则说明为非法格式。

当所有的括号都扫描完成之后,如果栈为空,则说明字符串为合法格式;否则,说明还有未匹配的左括号,为非法格式。

实现浏览器的前进、后退功能

我们使用两个栈,X和Y,我们把首次浏览的页面一次压入栈X,当点击后退按钮时,再一次从栈X中出栈,并将出栈的数据一次放入栈Y。当我们点击前进按钮时,我们依次从栈Y中取出数据,放入栈X中。当栈X中没有数据时,那就说明没有页面可以继续后退浏览了。当栈Y中没有数据,那就说明没有页面可以点击前进按钮浏览了。

比如顺序查看了a,b,c三个页面,我们就一次把a,b,c压入栈

image

当通过浏览器后退按钮,从页面c后退到页面a之后,我们就依次把c和b从栈X中弹出,并且依次放入到栈Y。

image

这个时候你又想看页面b,于是又点击前进页面回到b页面,我们就再把b从栈Y中出栈,放入栈X中。

image

这个时候,你通过页面b又跳转到新的页面d了,页面c就再也无法通过前进、后退按钮重复查看了,所以需要清空栈Y。

image

小结

栈是一种操作受限的数据结构,只支持入栈和出栈操作。后进先出是它的最大的特点。栈既可以通过数组实现,也可以通过链表来实现。不管基于数组还是链表,入栈、出栈的时间复杂度都为O(1)。

数据结构与算法四:链表(下)

astipsy阅读(12)

想写好链表并不是容易的事儿,尤其是那些复杂的链表操作,比如链表反转、有序链表合并等,写的时候非常容易出错。如果能熟练掌握这几个技巧,加上主动和坚持,轻松拿下链表代码完全没有问题。

一:理解指针或引用的含义

事实上,看懂链表的结构并不困难,但是一旦把它和指针混在一起,就容易让人摸不着头脑。所以,要想写对链表代码,首巡检就要理解好指针。

有些语言有“指针”的概念,比如C语言;有些语言没有指针,取而代之的是“引用”,比如Java、Python。不管是“指针”还是“引用”,实际上,它们的意思都是一样的,都是存储所指对象的内存地址。

对于指针的理解,我们只需要记住下面这句话就可以了:将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针中存储了这个变量的内存地址,指向了这个变量,通过指针就能找到这个变量。

在编写链表代码的时候,我们经常会有这样的代码:p->next=q。这行代码是说,p结点中的next指针存储了q结点的内存地址。

还有一个更复杂的,也是我们经常会有这样的代码:p->next=p->next->next。这行代码表示,p结点的next指针存储了p结点的下下一个结点的内存地址。

二:警惕指针丢失和内存泄露

不知道你有没有这样的感觉,写链表代码的时候,指针指来指去,一会儿就不知道指到哪里了。所以,我们在写的时候,一定注意不要丢了指针。

image

如图,我们希望在结点a和相邻结点b之间插入结点x,假设当前指针p指向结点a,如果我们将代码实现变成下面这个样子,就会发生指针丢失和内存泄露。

p->next = x;  // 将p的next指针指向x结点;
x->next = p->next;  // 将x的结点的next指针指向b结点;

p->next指针在完成第一步操作之后,已经不再指向结点b了,而是指向了结点x。第二行代码相当于将x复制给x->next,自己指向自己。因此,整个链表也就断成了两半,从结点b往后的所有结点都无法访问到了。

对于有些语言来说,比如C语言,内存管理是由程序员负责的,如果没有手动释放结点对应的内存空间,就会产生内存泄露。所以,我们插入节点时,一定要注意操作的顺序,要先将结点x的next指针指向结点b,再把结点a的next指针指向结点x,这样才不会丢失指针,导致内存泄露。所以,对于刚刚的插入代码,我们只需要把第一行和第二行代码的顺序颠倒一下就可以了。

同理,删除链表结点时,也一定要记得手动释放内存空间,否则,也会出现内存泄露的问题。

三:利用哨兵简化实现难度

首先,我们来回顾一下单链表的插入和删除操作。如果我们在结点p后面插入一个新的结点,只需要两行代码就可以搞定。

new_node->next = p->next;
p->next = new_node;

但是,当我们要向一个空链表中插入第一个结点,刚刚的逻辑就不能用了。我们需要进行下面这样的特殊处理,其中head表示链表的头结点。所以,从这段代码,我们可以发现,对于单链表的插入操作,第一个结点和后面的结点的插入逻辑是不一样的。

if (head == null) {
  head = new_node;
}

我们再来看单链表结点删除操作。如果要删除结点p的后继结点,我们只需要一行代码就可以搞定。

p->next = p->next->next;

但是,如果我们要删除链表中的最后一个结点,前面的删除代码就不能work了。跟插入类似,我们也需要对于这种情况特殊处理。

if (head->next == null) {
   head = null;
}

从前面的一步一步分析,我们可以看出,针对链表的插入、删除操作,需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。这样代码实现起来就会很繁琐,不简洁,而且也容易因为考虑不全而出错。

这个时候哨兵就要登场了。哨兵,解决的是国家质检的边界问题。同理,这里说的哨兵也是解决“边界问题”的,不直接参与业务逻辑。

还记得如何表示一个空链表吗?head=null 表示链表中没有结点了。其中head表示头结点指针,指向链表中的第一个节点。

如果我们引入哨兵结点,在任何时候,不管链表是不是空,head指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫做带头链表。相反,没有哨兵结点的链表就叫做不带头链表

如下图,哨兵结点是不存储数据的。因为哨兵结点一直存在,所以插入第一个结点和插入其它结点,删除最后一个结点和删除其它结点,都可以统一为想同的代码实现逻辑了。

image

实际上,这种利用单冰简化编程难度的技巧,在很多代码实现中都有用到,比如插入排序、归并排序、动态规划等。下面我们举一个非常简单的例子

代码一:

// 在数组a中,查找key,返回key所在的位置
// 其中,n表示数组a的长度
int find(char* a, int n, char key) {
  // 边界条件处理,如果a为空,或者n<=0,说明数组中没有数据,就不用while循环比较了
  if(a == null || n <= 0) {
    return -1;
  }

  int i = 0;
  // 这里有两个比较操作:i<n和a[i]==key.
  while (i < n) {
    if (a[i] == key) {
      return i;
    }
    ++i;
  }

  return -1;
}

代码二:

// 在数组a中,查找key,返回key所在的位置
// 其中,n表示数组a的长度
// 我举2个例子,你可以拿例子走一下代码
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 7
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 6
int find(char* a, int n, char key) {
  if(a == null || n <= 0) {
    return -1;
  }

  // 这里因为要将a[n-1]的值替换成key,所以要特殊处理这个值
  if (a[n-1] == key) {
    return n-1;
  }

  // 把a[n-1]的值临时保存在变量tmp中,以便之后恢复。tmp=6。
  // 之所以这样做的目的是:希望find()代码不要改变a数组中的内容
  char tmp = a[n-1];
  // 把key的值放到a[n-1]中,此时a = {4, 2, 3, 5, 9, 7}
  a[n-1] = key;

  int i = 0;
  // while 循环比起代码一,少了i<n这个比较操作
  while (a[i] != key) {
    ++i;
  }

  // 恢复a[n-1]原来的值,此时a= {4, 2, 3, 5, 9, 6}
  a[n-1] = tmp;

  if (i == n-1) {
    // 如果i == n-1说明,在0...n-2之间都没有key,所以返回-1
    return -1;
  } else {
    // 否则,返回i,就是等于key值的元素的下标
    return i;
  }
}

相比这两段代码,在字符串a很长的时候,比如几万、几十万,你觉得哪段代码运行得更快点呢?答案是代码二,因为两段代码中执行次数最多的就是while循环那部分。第二段代码中,我们通过一个哨兵 a[n-1]=key ,成功省掉了一个比较语句 i<n ,不要小看这一条语句,当积累执行万次、几十万次时,累积的时间就很明显了。

四:重点留意边界条件处理

软件开发中,代码在一些边界或者异常情况下,最容易产生Bug。链表代码也不例外。要实现没有Bug的链表代码,一定要在编写的过程中以及编写完成之后,检查边界条件是否考虑全面,以及代码在边界条件下是否能正确运行。

可以用以下四个边界条件来检查链表代码:

  • 如果链表为空时,代码是否能正常工作?
  • 如果链表只包含一个结点时,代码是否能正常工作?
  • 如果链表只包含两个结点时,代码是否能正常工作?
  • 代码逻辑在处理头结点和尾结点的时候,代码是否能正常工作?

当写完链表代码之后,除了看下是否能在正常的情况下工作,还要看下上面几个边界条件下,代码依然能否正确工作。如果这些边界条件下都没有问题,那基本上可以认为没有问题了。

五:举例画图,辅助思考

对于稍微复杂的链表操作,比如前面我们提到的单链表反转,指针一会儿指这,一会儿指那,一会儿就被绕晕了。总感觉脑容量不够,想不清楚。这时候就要使用大招了,举例法画图法

你可以照一个具体的例子,把它画在纸上,释放一些脑容量,留更多的给逻辑思考,这样就会感觉到思路清晰很多。比如往单链表中插入一个数据是这样的一个操作,我一般都是把各种情况都举一个例子,画出插入前和插入后的链表变化。

image

看图写代码,就简单多了。而且,当我们写完代码之后,也可以举几个例子,画在纸上,照着代码走一遍,很容易就能发现代码中的Bug。

六:多写多练,没有捷径

如果你已经理解并掌握了前面所讲的方法,但是手写链表代码还是会出现各种各样的错误,也不要着急。因为初学者刚开始学的时候,都是这种情况。把常见的链表操作都自己多写几遍,出问题就一点一点调试,熟能生巧。

这里精选了5个常见的链表操作,只要把这个几个操作都能写熟练,不熟就多谢几遍,保证你之后再也不会害怕写链表代码了。

  • 单链表反转
  • 链表中环的检测
  • 两个有序的链表合并
  • 删除链表倒数第n个结点
  • 求链表的中间结点

数据结构与算法四:链表(上)

astipsy阅读(11)

链表结构

相比数组,链表是一种稍微复杂一点的数据结构。数组和链表这两个非常基础、非常常用的数据结构,我们常常会放到一块儿来比较。

底层的存储结构来看。下图中,数组需要一块连续的内存空间来存储,对内存的要求较高。如果我们申请一个 100MB 大小的数组,当内存中没有连续的、足够大的存储空间时,即便内存的剩余总可用空间大于 100MB,仍然会申请失败。

而链表恰恰相反,它并不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用,所以如果我们申请的是 100MB 大小的链表,根本不会有问题。

image

链表结构五花八门,最常用的三种分别是:单链表双向链表循环链表

单链表

链表通过指针将一组零散的内存块串联在一起,其中,我们把内存块成为链表的“结点”。为了把所有的结点串起来,每个链表的结点除了存储数据之外,还要记录链表上的下一个结点的地址。我们把记录下个结点地址的指针叫做后继指针next

image

从图中可以发现,其中有两个结点是特殊的,它们分别是第一个和最后一个结点,我们习惯性的叫做头结点尾结点。头结点用来记录链表的基地址,有了它,我们就可以遍历得到整条链表。尾结点特殊的地方是:指针不是指向下一个结点,而是指向一个空地址NULL,表示这是链表上的最后一个结点。

在进行数组的插入、删除操作时,为了保证内存的连续性,需要做大量的搬移工作,所以时间复杂度是O(n)。而链表中的插入或者删除,我们并不需要为了保证内存的连续性而搬移结点,因为链表的存储空间本身就不是连续的。所以,在链表中的插入和删除是非常快速的。

针对链表的插入和删除,我们只需要考虑相邻结点的指针改变,所以对应的时间复杂度是O(1)。

image

但是,链表随机访问第k个元素,就没数组那么高效了。因为链表中的数据并非连续存储的,所以无法像数组那样根据寻址公式就能直接计算对应的内存地址,而是需要根据指针一个节点一个节点的依次遍历,直到找到相应的结点。

循环链表

循环链表是一种特殊的单链表,它跟单链表唯一的区别就在尾结点。单链表的尾结点指向一个空地址,表示这是最后的结点。而循环链表的尾结点指针指向的是头结点。

image

和单链表相比,循环链表的优势是从链尾到链头比较方便。当要处理的数据具有环形结构特点时,就特别适用采用循环链表,如约瑟夫问题

双向链表

单链表只有一个方向,结点只有一个后继指针next指向后面的结点。而双向链表支持两个方向,每个节点不止有一个后继指针next指向后面的结点,还有一个前驱指针prev指向前面的结点。

image

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以,如果存储同样多的数据,双向链表要比单链表占用更多的空间,虽然比较浪费空间,但可以支持双向遍历,这样也带来了双向链表操作的灵活性。

从结构上来说,双向链表可以支持O(1)时间复杂度的情况下找到前驱结点,正是这样的特别,也使双向链表在某些情况下的插入、删除等操作都要比单链表更简单、搞笑。

单链表和双向链表优势

在实际的软件开发中,从链表中删除一个数据无外乎两种情况:

  1. 删除节点中“值等于某个给定值”的结点
  2. 删除给定指针指向的结点。

对于第一种情况,不管是单链表还是双向链表,为了查找到值等于给定值的结点,都需要从头结点开始依次遍历对比,直到找到值等于给定值的结点,然后删除。

尽管单纯的删除操作时间复杂度是o(1),但遍历查找的时间是主要的耗时点,对应的时间复杂度为O(n)。所以总时间复杂度是O(n)。

对于第二种情况,我们已经找到了要删除的结点,但是删除某个结点q需要知道其前驱结点,而单链表不支持直接获取前驱结点,所以,为了找到前驱结点,我们还是要从头结点开始遍历链表,知道 p->next=q。

但是对于双链表来说,这种情况就比较有优势了。因为双链表中的结点已经保存了前驱结点的指针,不需要像单链表那样遍历。所以,针对第二种情况,单链表删除操作需要O(n)的时间复杂度,而双向链表只需要在O(1)的时间复杂度内就搞定了。

同理,如果我们希望在链表的某个结点前面插入一个结点,双向链表比单链表有很大优势。双向链表可以在O(1)时间复杂度搞定,而单链表需要O(n)的时间复杂度。

除了插入、删除操作有优势外,对于一个有序链表,双向链表的按值查询的效率也比单链表高。因为,我们可以记录上次查找的位置p,每次查询时,根据要查找的值与p的大小关系,决定往前还是往后查找,所以平均只需要查找一半的数据。

实际上,这里有一个更加重要的知识点,那就是用空间换时间的设计思想。当内存空间充足的时候,如果我们更加追求代码的执行速度,我们就可以选择空间复杂度相对较高、但时间复杂度相对较低的算法或者数据结构。相反,如果内存比较紧缺,比如代码跑在手机或者单片机上,这个时候,就要反过来用时间换空间的设计思路。

缓存设计

缓存实际上就是利用了空间换时间的设计思想。如果我们把数据存储在硬盘上,会比较节省内存,但每次查找数据都要询问一次硬盘,会比较慢。但如果我们通过缓存技术,事先将数据加载在内存中,虽然会比较耗费内存空间,但每次数据查询的速度就大大提高了。

所以,对于执行较慢的程序,可以通过消耗更多的内存(空间换时间)来进行优化;而消耗过多内存的程序,可以通过消耗更多的时间(时间换空间)来降低内存的消耗。

双向循环链表

如果把双向链表和循环链表整合在一起就有了一个新的版本:双向循环链表

image

链表和数组性能比较

数组和链表是两种截然不同的内存组织方式,正是因为内存存储的区别,它们的插入、删除、随机访问操作的时间复杂度正好相反。

image

但是,数组和链表的对比,并不能局限于时间复杂度。而且,在实际的软件开发中,不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。

数组简单易用,在实现上使用的是连续的内存空间,可以借助CPU的缓存机制,预读数组中的数据,所以访问效率更高。而链表在内存中并不是连续存储,所以对CPU缓存不友好,没有办法有效预读。

数组的缺点是大小固定,已经声明就要占用整块连续的内存空间。如果声明的数组过大,系统可能没有足够的内存空间分配给它,导致“内存不足(out of memory)”。如果生命的数组过小,则可能出现不够用的情况。这时只能再申请一个更大的内存空间,把原数组拷贝进去,非常耗时。链表本身没有大小的限制,天然的支持动态扩容。

如果你的代码对内存的使用非常苛刻,那数组就更适合你。因为链表中的每个节点都需要消耗额外的存储空间去存储一份指向下一个节点的指针,所以内存消耗会翻倍。而且,对链表进行频繁的插入、删除操作,会导致频繁的内存申请和释放,容易造成内存碎片,如果是Java语言,就有可能导致频繁的GC(Garbage Collection,垃圾回收)。

所以,在实际的开发中,针对不同类型的项目,要根据具体情况,权衡究竟是选择数组还是链表。

LRU缓存淘汰算法

如何继续链表实现 LRU 缓存淘汰算法?

思路:我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。

  1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,再插入到链表的头部。
  2. 如果此数据没有在缓存链表中,又可以分为两种情况:
    1. 如果此时缓存未满,则将此结点直接插入到链表的头部;
    2. 如果此时缓存已满,则链表尾结点删除,将新的数据插入链表的头部。

如此,我们就用链表实现了一个LRU缓存。

那么这个缓存访问的时间复杂度是多少呢?因为不管缓存有没有满,我们都需要遍历一遍链表,所以这种基于链表的实现思路,缓存访问的时间复杂度为O(n)。

数据结构与算法三:数组

astipsy阅读(15)

在大部分编程语言中,数组都是从0开始编号的,那么为什么数组要从0开始而不是1呢?带着这个问题我们来看下面的内容。

如何实现随机访问?

数组(Array)是一种线性表数据结构。它是用一组连续的内存空间,来存储一组具有相同类型的数据。

  1. 线性表,数据排成像一条线一样的结构。每个线性表上的数据最多只有前后两个方向。除了数组,链表、队列、栈等也是线性表结构。
    image

    而与它相对立的概念是非线性表,比如二叉树、堆、图等。之所以叫非线性表,是因为在非线性表中,数据之间并不是简单的前后关系。
    image

  2. 连续的内存空间和相同类型的数据。因为这两个限制,数组有了一个堪称“杀手锏”的特性:随机访问。但这两个限制也让数组的很多操作变得低效,比如在数组中删除、插入一个数据,为了保证连续性,就需要做大量的数据搬移工作。

    那么数组是如何实现下标随机访问数组元素的呢?拿一个长度为10的int类型的数组 int[] a = new int[10] 来举例。在下图中,计算机给数组 a[10] 分配了一块连续的内存空间 1000 ~ 1039 ,其中,内存块的首地址为base_address = 1000image

    我们知道,计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时,它会通过下面的寻址公式,计算出该元素存储的内存地址

    a[i]_address = base_address + i * data_type_size

    其中的 data_type_size 表示数组中每个元素的大小。我们举的这个例子中,数组存储的是 int 类型数据,所以 data_type_size 就为4个字节。

  3. 低效的“插入”和“删除”

    数组的插入操作,假设数组的长度为n,现在,我们要需要将一个数据插入到数组中的第k个位置。为了把第k个位置腾出来,给新来的数据,我们需要将k~n这部分的元素都顺序的往后挪一位。

    如果在数组的末尾插入数据,那就不需要移动数据了,这时的时间复杂度为O(1)。但如果在开头插入元素,所有的数据都需要往后移动一位,所以最欢的时间复杂度为O(n)。因此我们在每个位置插入元素的概率是一样的,所以平均时间复杂度为(1+2+...n)/n=O(n)。

    如果数组的数据是有序的,我们在某个位置插入元素的时候就需要用到刚才的方法。但是,如果数组中的数据是没有规律的,数组这是被当成一个存储数据的集合。这种情况下,如果要将某个数据插入到第k个位置,为了避免大规模的数据搬移,我们还有一个简单的办法,将第k位的数据搬移到数组元素的最后,把新的元素直接放入到第k个位置。

    为了更好的理解,我们假设数组 a[10] 中存储了5个元素:a,b,c,d,e。我们现在需要将元素x插入到第三个位置。那么我们只需要将c放入到 a[5] ,将 a[2] 赋值为 x 即可。image

    删除跟插入类似,我们要删除第k位的元素,为了内存的连续性,我们需要搬移数据,不让内存中间出现空洞不连续。删除末尾的数据,最好时间复杂度为O(1)。删除开头数据,最坏时间复杂度为O(n),平均时间复杂度也是O(n)。

    实际上,在某些特殊场景下,我们不一定非得追求数组中数据的连续性。

    例,数组 a[10] 中存储了8个元素:a,b,c,d,e,f,g,h。现在,我们要一词删除a,b,cimage

    为了避免d,e,f,g,h这个几个数据被搬移三次,我们可以先记录下已经删除的数据。每次的删除操作并不是真正的搬移工作,只是记录数据已经被删除。当数组没有更多空间存储数据时,我们再触发执行一次真正的删除操作,这样就大大减少了删除操作导致的数据搬移。这也是JVM标记清楚垃圾回收算法的核心思想。

警惕数组的访问越界问题

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

这段C语言代码中,运行结果并非是打印三行“hello world”,而是会无线打印“hello world”。

因为,数组大小为3,而我们的代码因为书写错误,导致for循环的结束条件写成了 i<=3 而非 i < 3,所以当 i=3 的时候,数组 a[3] 访问越界。

在C语言中,只要不是访问受限的内存,所有的内存空间都是可以自由访问的,根据我们的寻址公式,a[3] 也会被定为到某块不属于数组的内存地址上,而这个地址正好是存储变量i的内存地址,那么 a[3] = 0 就相当于 i=0,所以就会导致代码无限循环。

这种情况下,一般会出现莫名其面的逻辑错误,debug难度非常大。很多计算机病毒就是利用到了代码中的数组越界可以访问非法地址的漏洞来攻击系统,所以要警惕数组越界。

容器能否完全代替数组?

针对数组类型,很多语言都提供了容器类,比如Java中的ArrayList、C++ STL中的vector。在项目开发中,什么时候适合用数组,什么时候适合用容器呢?

我们用Java来说,ArrayList最大的优势是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外,它还有一个优势,支持动态扩容

数组本身在定义的时候需要预先指定大小,因为需要分配连续的内存空间。如果我们申请了大小为10的数组,当第11个数据需要存储到数组中时,我们就需要分配一块更大的空间,将原来的数据复制过去,然后插入新的数据。

如果使用ArrayList,我们就不需要关心底层的扩容逻辑了,每次存储空间都不够的时候,它都会将空间自动扩容为1.5倍大小。

但是,扩容操作涉及内存申请和数据搬移,是比较耗时的,所以最好在创建ArrayList的时候事先指定数据大小。

作为高级语言编程者,是不是数组就无用武之地了呢?当然不是,有些时候,用数组会更合适:

1. Java ArrayList无法存储基本类型,比如int、long,需要封装为Integer、Long类,而 Autoboxing、Unboxing 则有一定的性能消耗,所以如果特别关注性能,或者希望使用基本类型,就可以选用数组。
2. 如果事先知道数据大小,并且对数据的操作非常简单,且用不到ArrayList提供的大部分方法,也可以直接使用数组。
3. 当要表示多维数组时,用数组往往会更加直观。比如Object[][] array;而用容器的话则需要这样定义:ArrayList<ArrayList<object>> array。

为什么数组从0开始编号

从数组存储的内存模型上来看,“下标”最确切的定义应该是“偏移(offset)”。如果a来表示数组的首地址,a[0]就是偏移为0的位置,也就是首地址,a[k]就是表示偏移了k个type_size的位置

a[k]_address = base_address + k * type_size

但是,如果数组从1开始计数,那我们计算数组元素a[k]的内存地址就会变为:

a[k]_address = base_address + (k-1)*type_size

通过这两个公式,我们不难看出,从1开始编号,每次随机访问数组元素都多了一次减法运算,对于CPU来说,就多了一次减法指令。

数组作为非常基础的数据结构,通过下标随机访问数组元素又是其非常基础的编程操作,效率的优化就要尽可能坐到极致。所以为了减少一次减法操作,数组选择了从0开始编号,而不是从1开始。

不过我认为,上面解释得再多其实都算不上压倒性的证明,说数组起始编号非 0 开始不可。所以我觉得最主要的原因可能是历史原因。C 语言设计者用 0 开始计数数组下标,之后的 Java、JavaScript 等高级语言都效仿了 C 语言,或者说,为了在一定程度上减少 C 语言程序员学习 Java 的学习成本,因此继续沿用了从 0 开始计数的习惯。实际上,很多语言中数组也并不是从 0 开始计数的,比如 Matlab。甚至还有一些语言支持负数下标,比如 Python。

小结

数组是最基础也是最简单的数据结构了,数组用一块连续的内存空间来存储相同类型的一组数据,最大的特点是支持随机访问,但插入、删除操作也因此变得比较低小,平均情况时间复杂度为O(n)。在平时的业务开发中,我们可以直接使用编程语言提供的容器类,但是,如果是特别底层的开发,直接使用数组可能会更合适。

数据结构与算法二:复杂度分析(下)

astipsy阅读(15)

上一节中我们掌握了一些常见的复杂度,如O(1)、O(logn)、O(n)、O(nlogn)。下面我们继续四个复杂度分析方面的知识点:最好情况时间复杂度(best case time complexity)最坏情况时间复杂度(worst case time complexity)平均情况时间复杂度(average case time complexity)均摊时间复杂度(amortized time complexity)

最好、最坏情况时间复杂度

// n表示数组array的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) pos = i;
  }
  return pos;
}

从上面的代码可以很轻易的看出时间复杂度为O(n),但是这段代码不够高效,下面这段代码是优化之后的

// n表示数组array的长度
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;
}

当我们优化完代码之后,时间复杂度就不再是O(n)了。

因为x可能处于数组的任意位置。如果数组中的第一个位置就是x,那么时间复杂度就是O(1);如果数组中不存在x,那么我们就需要把整个数组都循环一次,时间复杂度就是o(n)。所以,不同情况下的时间复杂度是不一样的。

为了表示这种情况,我们引入了三个概念:最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度

平均时间复杂度

最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度,发生的概率并不大。为了更好的表示平均情况下的复杂度,我们需要引入另外一个概念:平均情况时间复杂度

上一段代码中,我们要查找x的位置,有n+1种情况:在数组的0~n-1位置中和不在数组中。我们把每种情况下,查找需要遍历的元素个数累加起来,除以n+1,就可以得到需要遍历的元素个数的平均值

image

根据时间复杂度标记法,我们可以忽略掉系数、低阶、常量,所以,简化之后得到的平均时间复杂度就是O(n)。

但是我们知道,要查找的变量x,要么在数组里,要么不在数组里,这两种情况的概率都为1/2。另外,在0-(n-1)这个n个位置的概率是1/n。所以,根据概率乘法法则,要查找的数据出现在0-(n-2)中任意位置的概率就是1/(2n)

所以,前面推导过程中存在的最大问题是,没有将各种情况发生的概率都考虑进去。如果都考虑进去,平均时间复杂度的计算过程就会变成这样:image

这个值就是概率论中的加权平均值,也叫期望值,所以平均时间复杂度的全称也叫加权平均时间复杂度或者期望时间复杂度

当我们去掉系数和常量后,这段代码的加权平均时间复杂度仍然是O(n)

实际上,大多数情况下我们并不需要区分最好、最坏、平均情况时间复杂度三种情况。很多时候,我们使用一个复杂度就可以满足需求了。只有同一块代码在不同情况下,时间复杂度有量级的差距,我们才会使用这三种复杂度表示法来区分。

均摊时间复杂度

均摊时间复杂度,听起来跟平均时间复杂度有点像,对于初学者来说,这两个概念确实非常容易混淆。其实大部分情况下,我们并不需要区分最好、最坏、平均三种复杂度。平均复杂度只在某些特殊情况下才会用到,而均摊时间复杂度应用的场景更加特殊、更加有限。

 // array表示一个长度为n的数组
 // 代码中的array.length就等于n
 int[] array = new int[n];
 int count = 0;

 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

这段代码实现了一个往数组中插入数据的功能。当数组满了,即count == array.length的时候,我们对数组内的所有元素求和,然后清空数组,讲求和的数组插入到数组的第一个位置,然后再插入新的数据。但如果数组一开始就有空闲空间,则直接将数据插入到数组。

这段代码的时间复杂度是多少呢?我们先用前面讲到的三种时间复杂度来分析一下

最理想的状态下,数组中有空闲空间,可以直接进行数据插入,所以最好时间复杂度是O(1)。最坏的情况下,数组没有空闲空间,我们要先做一遍数组遍历求和再插入数据,所以最坏时间复杂度是O(n)。

平均时间复杂度是O(1)。我们来分析一下:数组长度为n,在数组有空闲空间的情况下,每种情况的时间复杂度都为O(1),在数组没有空闲空间的情况下,时间复杂度为O(n)。这n+1种情况发生的概率都一样,都是1/(n+1)。所以,根据加权平均的计算方法,我们求得的平均时间复杂度是:
image

至此,三种复杂度分析完了。但是这个例子里的平均时间复杂度分析其实并不需要那么复杂,不需要引入概率论知识。我们先来对比一下这个insert()和find()。

首先,find()在极端情况下复杂度才为O(1),而insert()在大部分情况下都为O(1),只有在个别情况下为O(n)。这是第一个区别。

第二个区别,对于insert()来说,O(1)时间复杂度的插入和O(n)时间复杂度的插入,出现的频率是非常有规律的,而且有一定的前后时序关系,一般都是一个O(n)插入之后,紧跟着n-1个O(1)插入,循环往复。

所以,针对这种特殊场景的复杂度分析,我们不需要再根据之前的平均复杂度那样分析了,这里韵如一种更加简单的分析方法:摊还分析法,通过摊还分析得到的时间复杂度我们起了一个名字,叫均摊时间复杂度

在insert()中,每一次O(n)的插入操作,都会跟着n-1次O(1)的插入操作,所以把耗时多的那次操作均摊到接下来的n-1次耗时少的操作上,均摊下来,这一组连续的操作的均摊时间复杂度就是O(1)。这就是均摊分析的大致思路。

均摊时间复杂度和摊还分析应用场景比较特殊,所以我们并不会经常用到。

对一个数据结构进行一组连续的操作时,大部分情况下的时间复杂度都很低,只有个别情况下时间复杂度比较高,而且这些操作都存在前后连贯的时序关系,这个时候我们可以将这一组操作放在一块儿分析,看是否能将最高时间复杂度那次操作的耗时,均摊到其他时间复杂度比较低的操作上。而且,在能够应用均摊时间复杂度分析的场合,一般均摊时间复杂度就等于最好情况复杂度。

数据结构与算法二:复杂度分析(上)

astipsy阅读(12)

复杂度分析的必要性

通过跑代码得到算法执行的时间和占用空间局限性非常大,其测试结果非常依赖测试环境,测试结果也受数据规模的影响很大,所以我们需要一个不用具体的测试数据来测试,就可以粗略的估计算法的执行效率的方法。

大O复杂度表示法(时间复杂度)

大O复杂度表示法并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫渐进时间复杂度,简称时间复杂度。

时间复杂度可以由以下三个比较实用的方法来分析

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

    我们在分析一个算法、一段代码的时间复杂度的时候,也只关注循环次数最多的那段代码就可以了

    int cal(int n) {
    int sum = 0;
    int i = 1;
    for (; i <= n; ++i) {
     sum = sum + i;
    }
    return sum;
    }

    当n很大时,可以想象成10000,1000000。而代码中的低阶、常量、系数三个部分并不左右增长趋势,所以可以忽略。我们只需要记录一个最大量级就可以了。

    第二三行都是常量级的执行时间,与n的大小无关,所以对于时间复杂度没有影响。执行时间最多的是第四五行代码,都被执行了n次,所以时间复杂度为O(n)

  2. 加法法则,总复杂度等于量级最大的那段代码的复杂度

    int cal(int n) {
    int sum_1 = 0;
    int p = 1;
    for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
    }
    
    int sum_2 = 0;
    int q = 1;
    for (; q < n; ++q) {
     sum_2 = sum_2 + q;
    }
    
    int sum_3 = 0;
    int i = 1;
    int j = 1;
    for (; i <= n; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
    }
    
    return sum_1 + sum_2 + sum_3;
    }

    这段代码分为三个部分,sum_1、sum_2、sum_3,我们可以分析每一部分的时间复杂度,然后把它们放到一块儿,再取一个量级最大的作为整段代码的时间复杂度。

    第一部分执行了100次,所以是一个常量的执行时间,与n的规模无关,所以这里的时间复杂度记为O(1)

    第二部分时间复杂度 O(n),第三部分时间复杂度 O(n²)。综合三段代码,取其中最大的量级,所以这段代码的时间复杂度为O(n²)

  3. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

    int cal(int n) {
    int ret = 0; 
    int i = 1;
    for (; i < n; ++i) {
     ret = ret + f(i);
    } 
    } 
    
    int f(int n) {
    int sum = 0;
    int i = 1;
    for (; i < n; ++i) {
    sum = sum + i;
    } 
    return sum;
    }

    单看cal函数,时间复杂度为O(n)。但f函数不是一个简单的操作,f函数的时间复杂度可以看出为O(n),所以,整个cal函数内的时间复杂度为两个复杂度的成绩O(n²)

几种常见的时间复杂度分析

以下几种复杂度量级几乎涵盖了所有代码的复杂度量级

image

以上罗列的复杂度量级,我们可以粗略的分为两类,多项式量级和非多项式量级。非多项式量级只有两个:O(2ⁿ)、O(n!)

当n越来越大时,非多项式量级算法的执行时间会急剧增加,执行时间会无限增长,所以非多项式时间复杂度的算法其实是非常抵消的。因此我们主要来看几种多项式时间复杂度

  1. O(1)
    首先要明确一个概念,O(1)这是常量级时间复杂度的一种表示方式,并不是指只执行了一段代码

    int i = 8;
    int j = 6;
    int sum = i + j;

    一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行代码,时间复杂度也是O(1)

  2. O(logn)、O(nlogn)

    i=1;
    while (i <= n)  {
    i = i * 2;
    }

    从代码中看出,i从1开始取,每循环一次乘以2,由此得出:
    image
    所以,我们只需要知道x是多少,就能知道这段代码的执行次数了。通过2^x=n可以得出,x=log(2)n,所以这段代码的时间复杂度为log(2)n。

    我们知道,对数之间是可以互相转换的 log(3)n = log(3)2 log(2)n,所以O(log(3)n) = O(log(3)2 log(2)n),其中Log(3)2是常量,可以忽略系数,所以log(3)n = log(2)n。

    在对数的时间复杂度的表示法里,我们忽略对数的底,统一表示为O(logn)。所以这段代码的最终时间复杂度为O(logn)

    利用乘法法则,我们可以很轻易的了解到O(nlogn),即如果一段时间复杂度为O(logn)的代码执行了n次,时间复杂度就为O(nlogn)了。O(nlogn)是一种非常常见的时间复杂度,比如,归并排序、快速排序。

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

    int cal(int m, int n) {
    int sum_1 = 0;
    int i = 1;
    for (; i < m; ++i) {
    sum_1 = sum_1 + i;
    }
    
    int sum_2 = 0;
    int j = 1;
    for (; j < n; ++j) {
    sum_2 = sum_2 + j;
    }
    
    return sum_1 + sum_2;
    }

    这段代码分为两个部分,第一部分的时间复杂度为O(m),第二部分的时间复杂度为O(n)。但我们无法评估m和n谁的量级大,所以我们在表示时间复杂度的时候,就不能简单的利用加法法则省略掉其中一个。所以,这段代码的时间复杂度为O(m+n)。

    这种情况的加法法则就不正确了,时间复杂度改为了m+n,但乘法法则依然有效。

空间复杂度分析

时间复杂度的全称是渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系。类比一下,空间复杂度全称是渐进空间复杂度,表示算法的存储空间与数据规模之间的增长关系。

void print(int n) {
  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }

  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}

从第二行代码可以看出,我们申请了一个空间存储变量i,但它是常量阶的,跟数据规模n无关,所以我们可以忽略。第三行申请了一个大小为n的int类型数组,除此之外,剩下的代码都没有占用更多的空间,所以整段代码的空间复杂度为O(n)。

我们常见的空间复杂度有O(1)、O(n)、O(n²),像 O(logn)、O(nlogn)这样的对数阶复杂度平时都用不到

总结

复杂度也叫渐进复杂度,包括时间和空间,用来分析算法执行效率与数据规模之间的增长关系,可以粗略的表示,越高阶复杂度的算法,执行效率越低。常见的复杂度并不多,从低阶到高阶有:O(1)、O(logn)、O(n)、O(nlogn)、O(n²)

数据结构与算法一:初识

astipsy阅读(12)

什么是数据结构?什么是算法?

  1. 广义概念

数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法

  1. 狭义概念

指某些著名的数据结构和算法,比如队列、栈、堆、二分查找、动态规划等。这些经典数据结构和算法,都是前人从很多实际操作场景中抽象出来的,经过非常多的求证和检验,可以高效的帮助我们解决很多实际的开发问题。

学习重点

  1. 复杂度分析

复杂度分析占据了数据结构和算法的半壁江山,是数据结构和算法的精髓。

数据结构和算法解决的是如何更省、更快的存储和处理数据的问题,因此,我们就需要一个考量效率和资源消耗的方法,这就是复杂度分析方法。

  1. 正文
    image

图中包含了所有数据结构和算法书籍中都会讲到的知识点。

作为初学者,或者非算法工程师,并不需要掌握图中的所有知识点。

以下20个是最常用、最基础的数据结构和算法:

  • 10个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树
  • 10个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法

RabbitMQ的实现

astipsy阅读(30)

点击查看RabbitMQ教程

生产者:

$config = [
    'host' => '127.0.0.1',
    'vhost' => 'rabbitmqhost',
    'port' => 5672,
    'login' => 'admin',
    'password' => '123456'
];

$exchangeName = 'kd_sms_send_ex'; //交换机名
$queueName = 'kd_sms_send_q'; //队列名称
$routingKey = 'sms_send'; //路由关键字(也可以省略)

// 建立生产者与mq之间的连接
$conn = new AMQPStreamConnection(
    $config['host'], $config['port'], $config['login'], $config['password'], $config['vhost']
);
// 在已连接基础上建立生产者与mq之间的通道
$ch = $conn->channel();

// 声明初始化交换机
$ch->exchange_declare($exchangeName, 'direct', false, true, false);
// 声明初始化一条队列
$ch->queue_declare($queueName, false, true, false, false);
// 将队列与某个交换机进行绑定,并使用路由关键字
$ch->queue_bind($queueName, $exchangeName, $routingKey);

$msgBody = json_encode(["name" => "iGoo", "age" => 22]);
// 生成消息
$msg = new AMQPMessage($msgBody, ['content_type' => 'text/plain', 'delivery_mode' => 2]);  
// 推送消息到某个交换机
$ch->basic_publish($msg, $exchangeName, $routingKey);

消费者:

$config = [
    'host' => '127.0.0.1',
    'vhost' => 'rabbitmqhost',
    'port' => 5672,
    'login' => 'admin',
    'password' => '123456'
];

// 交换机名
$exchangeName = 'kd_sms_send_ex'; 
// 队列名称
$queueName = 'kd_sms_send_q'; 
// 路由关键字(也可以省略)
$routingKey = 'sms_send'; 

// 建立生产者与mq之间的连接
$conn = new AMQPStreamConnection(
    $config['host'], $config['port'], $config['login'], $config['password'], $config['vhost']
);
// 在已连接基础上建立生产者与mq之间的通道
$ch = $conn->channel();

// 声明初始化一条队列
$ch->queue_declare($queueName, false, true, false, false);

// 在接收消息的时候调用回调函数
$ch->basic_consume($queueName, '', false, true, false, false, function ($msg){
   vdump(" [x] Received ", $msg->body, "\n");
});

// 堵塞
while(count($ch->callbacks)) {
   $ch->wait();
}

PHPstorm常用快捷键

astipsy阅读(49)

CTRL+N 查找类
CTRL+SHIFT+N 全局搜索文件 ,优先文件名匹配的文件
CTRL+SHIFT+ALT+N 查找php类名/变量名 ,js方法名/变量名, css 选择器
CIRL+B 找变量的来源,跳到变量申明处
CTRL+G 定位行,跳转行
CTRL+J 自动代码提示,自动补全
ALT+回车 导入包,自动修正
CTRL+ALT+L 格式化代码
CTRL+ALT+I 自动缩进
CTRL+ALT+SPACE 类名或接口名提示(与系统冲突) 提示类名关键字 (abstract public ...)
CTRL+P 方法参数提示,显示默认参数
CTRL+ALT+O 优化导入的类和包 需要配置
CTRL+W 块状选中代码