数据结构之一组图让你搞懂时间复杂度-php教程

资源魔 2020-07-10 20:02:22 27 0

本篇文章中经过一组图片让你轻松明确甚么是工夫复杂度，风趣生动，具备肯定学习代价，感兴味的冤家快来理解一下吧。

640?wx_fmt=jpeg

工夫复杂度的意思

终究甚么是工夫复杂度呢？让咱们来设想一个场景：某一天，小灰以及年夜黄同时退出了一个公司......

640?wx_fmt=jpeg

一天当时，小灰以及年夜黄各自交付了代码，两端代码完成的性能都差没有多。年夜黄的代码运转一主要花100毫秒，内存占用5MB。小灰的代码运转一主要花100秒，内存占用500MB。于是......

640?wx_fmt=jpeg

因而可知，权衡代码的优劣，包罗两个十分首要的目标：

1.运转工夫；

2.占用空间。

640?wx_fmt=jpeg

根本操作执行次数

对于代码的根本操作执行次数，咱们用四个生存中的场景，来做一下比喻：

场景1：给小灰一条长10寸的面包，小灰每一3天吃掉1寸，那末吃掉整个面包需求几天？

640?wx_fmt=jpeg

谜底天然是 3 X 10 = 30天。

假如面包的长度是 N 寸呢？

此时吃掉整个面包，需求 3 X n = 3n 天。

假如用一个函数来表白这个绝对工夫，能够记作 T（n） = 3n。

场景2：给小灰一条长16寸的面包，小灰每一5天吃掉面包残余长度的一半，第一次吃掉8寸，第二次吃掉4寸，第三次吃掉2寸......那末小灰把面包吃患上只剩下1寸，需求几何天呢？

这个成绩翻译一下，就是数字16一直地除了以2，除了几回当前的后果等于1？这里要触及到数学傍边的对数，以2位底，16的对数，能够简写为log16。

因而，把面包吃患上只剩下1寸，需求 5 X log16 = 5 X 4 = 20 天。

假如面包的长度是 N 寸呢？

需求 5 X logn = 5logn天，记作 T（n） = 5logn。

场景3：给小灰一条长10寸的面包以及一个鸡腿，小灰每一2天吃掉一个鸡腿。那末小灰吃掉整个鸡腿需求几何天呢？

640?wx_fmt=jpeg

谜底天然是2天。由于只说是吃掉鸡腿，以及10寸的面包不关系。

假如面包的长度是 N 寸呢？

无论面包有多长，吃掉鸡腿的工夫依然是2天，记作 T（n） = 2。

场景4：给小灰一条长10寸的面包，小灰吃掉第一个一寸需求1地利间，吃掉第二个一寸需求2地利间，吃掉第三个一寸需求3地利间.....每一多吃一寸，所花的工夫也多一天。那末小灰吃掉整个面包需求几何天呢？

谜底是从1累加到10的总以及，也就是55天。

假如面包的长度是 N 寸呢？

此时吃掉整个面包，需求 1+2+3+......+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n。

记作 T（n） = 0.5n^2 + 0.5n。

640?wx_fmt=jpeg

下面所讲的是吃货色所破费的绝对工夫，这一思维一样实用于对顺序根本操作执行次数的统计。方才的四个场景，辨别对应了顺序中最多见的四种执行形式：

场景1：T（n） = 3n，执行次数是线性的。

void eat1(int n){
    for(int i=0; i<n; i++){;
        System.out.println("期待一天");
        System.out.println("期待一天");
        System.out.println("吃一寸面包");
    }
}
vo

场景2：T（n） = 5logn，执行次数是对数的。

void eat2(int n){
   for(int i=1; i<n; i*=2){
       System.out.println("期待一天");
       System.out.println("期待一天");
       System.out.println("期待一天");
       System.out.println("期待一天");
       System.out.println("吃一半面包");
   }
}

场景3：T（n） = 2，执行次数是常量的。

void eat3(int n){
   System.out.println("期待一天");
   System.out.println("吃一个鸡腿");
}

场景4：T（n） = 0.5n^2 + 0.5n，执行次数是一个多项式。

void eat4(int n){
   for(int i=0; i<n; i++){
       for(int j=0; j<i; j++){
           System.out.println("期待一天");
       }
       System.out.println("吃一寸面包");
   }
}