loader image

数据结构–时间复杂度

408
6
数据结构
5
数据结构到底在学什么？（开篇）
数据结构绪论
算法基本概念
数据结构--时间复杂度
数据结构--空间复杂度
计算机组成原理
0
操作系统
0
计算机网络
0
408简介

前言

当你拿到一段代码时，你该如何判断这一段代码算法的好坏程度？

有的人会说跑一下（运行一下），事后统计运行时间。当然这样确实能够直观的通过看运行程序所花费时间，但是这存在着一些问题：

  • 和机器性能有关
    • 超级计算机 vs 单片机（同样的一段代码一定是超级计算机运行的时间更快）
  • 和编程语言有关
    • 越高级的语言运行的效率越低
  • 编译程序产生的机器指令质量有关
  • 有些算法不能事后统计
    • 导弹控制算法（不能为了统计算法的效率发射一颗导弹试试）

所以综上，如果使用事后统计（先运行一下）的方法，算法运行的速度除了和自身算法的优劣有关，还和许多的外界因素有关。并且从上我们可以提出两个问题：

  • 能否排除外界与算法本身无关的因素？
  • 能否事先估计？

至此我们引入了一个概念：算法复杂度

算法时间复杂度

含义

事前预估算法时间开销T(n)与问题规模n的关系（T代表时间“Time”）

爱你三千遍

我们使用一段简单的代码来解释时间复杂度

#include<stdio.h>

void loveU(int n){ // n为问题规模
    int  i = 1;
    while(i<=n){
        printf("I love you %d\n times",i);
        i++;
    }
    printf("I love you more than %d\n",n);
}

int main(){
    loveU(3000);
}

代码分析

在主函数中，我们调用loveU()函数，并且传入问题规模n（3000）

我们看loveU()函数中的5条语句频度

int i = 1 // 执行1次
while(i<=n){ // 执行3001次
    printf("I love you %d\n",n); // 执行3000次
    i++; // 执行3000次
}
printf("I love you more than %d\n",n); // 执行1次

故：$T(3000) = 1+ 3001 + 3000*2 + 1$，得出时间开销与问题规模n的关系：$T(n) = 3n +3$

推导过程：

1 + 3001 + 3000*2 + 1

-> (3001->3000+1) 1 + 1 + 1 + 3000*3

问题1：是否可以忽略表达式某些部分？

上述的例子中，问题规模n与时间开销的关系还算比较简单。

但是如果有一个表达式是：$T(n)=n^3+6n^2+n+1500$ 那么我们就很难一眼看出其复杂度。那么我们就会提出一个问题，是否可以忽略表达式某些部分呢？

回答1：可以忽略表达式某些部分

答案是肯定的，我们可以忽略表达式的某些部分。

忽略低阶保留最高阶（数量级）

要回答这个问题，我们可以通过上述的例子来理解：

当$n=3000$时：

$3n=9000$ vs $3n+3=9003$

$n^2=9000000$ vs $n^2+3n+1000=9010,000$

$n^3=27000000000$ vs $n^3+n^2+9999999=270189999999$

从上述的数据中我们可以看出，横向的结果差距并不大，而竖向的差距却很大。也就是说当我们的问题规模足够大时，低阶的数据在高阶的数据面前不值得一提。下面我们使用极限来证明：

$\lim{n \to \infty}\frac{n^2}{n^3}=>\lim{n \to \infty}\frac{1}{n}=0$

由此，我们可以得出结论：忽略低阶保留最高阶。也就是俗称的抓大头。也就是我们俗称的数量级。

$T(n)=n^3+6n^2+n+1500$ 中$n^3$在式子中是为最高次，所以时间复杂度的表达式就可以简化成$T(n)=n^3$

系数变为1

在这里我想问大家一个问题，$3n和n$的时间复杂度谁高？

许多小伙伴可能会不约而同的说$3n$的复杂度高，当$n=3000$时，$3n=9000 n=3000$ 但是并不是这样的，它们的时间复杂度应该是一样的。

我们仍可以对保留最高阶的表达式进一步的简化——将其系数变为1

如果有一个式子为$T(n)=3n^3+n^2+n+1000$ 我们需要对其化简：

  1. 保留最高阶 -> $T(n)=3n^3$
  2. 将系数变为1 -> $T(n)=n^3$

注意：

常数的系数变为1就是整个常数化为1

9000 -> 1

大O表示法

同时我们可以将时间复杂度使用大O表示法表示：

$n^3=O(n^3)$

$n^2 = O(n^2)$

$1=O(1)$

大O表示同阶（同等数量级），即：当n->∞时，二者之比为常数：

$lim{n\to\infty}\frac{3n^2}{n^2}=3$

运算法则

加法规则

$T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$（保留最高阶，且系数变1）

由于加法规则中是保留最高阶，那么到底结束之间是什么关系呢？

$O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$

以上就是各种表达式的阶数高低排列。当然如果你真的忘记了可以使用极限的知识去推理：

image-20220626205056715

也可以使用一些小妙招：

$O(n^3)和O(n^2log_2n)$比较阶数，可以先将$n^3=n^2n,n^2与n^2$同阶，$n的阶数比log_2n$低，故$O(n^2log_2n)$的阶数更高

我们给出一张图可以更直观的看出时间复杂度（该图截自于王道计算机考研——数据结构）

image-20220626205841343

口诀

常对幂指阶。这句口诀能更加快速的记忆阶数的高低。

乘法规则

$T(n)=T_1(n)×T_2(n)=O(f(n))×O(g(n))=O(f(n)×g(n))$（都保留）

问题2：如果有好几千行代码，按这种方法需要一行一行数吗？

在爱你三千遍的例子中，我们是逐行分析代码，最后写出了时间复杂度。刚刚的代码仅仅只有五行，逐行分析并没有太大的困难，但是当代码有上千行甚至上万行时，这种方法就显得非常复杂了。

分析循环

不过好消息是，我们并不需要逐行分析。我们通过上述的代码可以了解到，如果代码中不存在循环，那么就是有几行代码，执行次数就+1。那么时间复杂度就是常数，我们又在上面讲过，系数变为1。如果并未存在循环那么时间复杂度就是$O(1)$

#include<stiod.h>

int main(){
    printf("1");
    printf("2");
    printf("3");
}

上述的程序的时间复杂都就是3，我们将系数变为1后时间复杂度变为：$O(1)$

如果代码中存在单层循环，则分析单层循环。单层循环复杂度为$O(n)$

#include<stiod.h>

int main(){
    int n = 3;
    for(int i;i<=n;i++){
        printf("%d",i);
        i++;
    }
}

上述代码中有一个一层的for循环，外层的int n = 3语句的时间复杂度为$O(1)$，单层循环的复杂度为$O(2n)$，$O(2n)+O(1)$，于是最终保留最高阶$O(2n)$，再将系数变为1 $O(n)$

如果代码中存在多层循环（此处以二层为例），则二层循环的时间复杂度为$(O(n^2))$

综上：

  1. 如果代码中不存在循环，那么时间复杂度为$O(1)$
  2. 如果代码中存在单层循环，那么时间复杂度为$O(n)$
  3. 如果代码中存在n层循环，那么时间复杂度为$O(n^n)$

换句话说，我们只需要看算法中的最深的循环有多少层即可，并不需要逐行分析。

结束语

希望本文能够帮助到你 🙂

155人评论了“数据结构–时间复杂度”

  3. nordvpn special coupon code 2024

    Hey would you mind sharing which blog platform you’re working with?
    I’m planning to start my own blog soon but I’m having a difficult
    time making a decision between BlogEngine/Wordpress/B2evolution and Drupal.
    The reason I ask is because your layout seems different then most blogs and I’m looking for something completely unique.

    P.S My apologies for being off-topic but I had to ask!

    My blog nordvpn special coupon code 2024

  10. Ремонт телефонов

    Профессиональный сервисный центр по ремонту сотовых телефонов, смартфонов и мобильных устройств.
    Мы предлагаем: ремонт телефонов
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  11. Ремонт телефонов

    Профессиональный сервисный центр по ремонту сотовых телефонов, смартфонов и мобильных устройств.
    Мы предлагаем: ремонт смартфонов москва
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  12. ремонт квадрокоптера

    Профессиональный сервисный центр по ремонту квадрокоптеров и радиоуправляемых дронов.
    Мы предлагаем:сервис по ремонту квадрокоптеров
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  19. ремонт ipad в москве

    Профессиональный сервисный центр по ремонту радиоуправляемых устройства – квадрокоптеры, дроны, беспилостники в том числе Apple iPad.
    Мы предлагаем: ремонт камеры квадрокоптера
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  21. ремонт техники в спб

    Профессиональный сервисный центр по ремонту бытовой техники с выездом на дом.
    Мы предлагаем:ремонт крупногабаритной техники в петрбурге
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  30. Ремонт варочных панелей

    Профессиональный сервисный центр по ремонту варочных панелей и индукционных плит.
    Мы предлагаем: надежный сервис ремонта варочных панелей
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  31. ремонт техники в екб

    Профессиональный сервисный центр по ремонту бытовой техники с выездом на дом.
    Мы предлагаем:сервис центры бытовой техники екатеринбург
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  34. Ремонт фотоаппаратов в Москве

    Профессиональный сервисный центр по ремонту фото техники от зеркальных до цифровых фотоаппаратов.
    Мы предлагаем: ремонт фотоаппаратов
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  37. ремонт техники в новосибирске

    Профессиональный сервисный центр по ремонту бытовой техники с выездом на дом.
    Мы предлагаем:сервисные центры по ремонту техники в новосибирске
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  44. Ремонт стиральных машин в Москве

    Профессиональный сервисный центр по ремонту стиральных машин с выездом на дом по Москве.
    Мы предлагаем: срочный ремонт стиральных машин в москве
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  45. ремонт техники в казани

    Профессиональный сервисный центр по ремонту бытовой техники с выездом на дом.
    Мы предлагаем: ремонт крупногабаритной техники в казани
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  47. ремонт бытовой техники в москве

    Профессиональный сервисный центр по ремонту бытовой техники с выездом на дом.
    Мы предлагаем: ремонт крупногабаритной техники в москве
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  49. Ремонт игровых консолей

    Профессиональный сервисный центр по ремонту игровых консолей Sony Playstation, Xbox, PSP Vita с выездом на дом по Москве.
    Мы предлагаем: срочный ремонт игровой консоли
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  51. Ремонт фотовспышек в Москве

    Профессиональный сервисный центр по ремонту фототехники в Москве.
    Мы предлагаем: мастер по ремонту фотовспышек
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!
    Подробнее на сайте сервисного центра remont-vspyshek-realm.ru

  52. Ремонт ПК

    Профессиональный сервисный центр по ремонту компьютероной техники в Москве.
    Мы предлагаем: чинить компьютер
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  53. Ремонт блоков питания в Москве

    Профессиональный сервисный центр по ремонту компьютерных блоков питания в Москве.
    Мы предлагаем: ремонт блоков питания москва
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  54. Купить раковину

    Недавно нашёл отличный интернет-магазин, где можно приобрести раковины и ванны для ванной комнаты. Они предлагают огромный выбор сантехники и аксессуаров, подходящих под любой интерьер и бюджет. Ассортимент действительно впечатляет: различные модели раковин (накладные, встроенные, подвесные) и ванн (акриловые, чугунные, гидромассажные).
    Особенно если вы ищете: каталог раковин, что мне было очень нужно. Цены адекватные, качество товаров на высоте. Плюс, они предлагают профессиональные консультации, быструю доставку и услуги по установке. В общем, если кто-то ищет качественную сантехнику по хорошим ценам, рекомендую обратить внимание на этот магазин.

  55. ремонт телефонов москва

    Сломался телефон, думал покупать новый, но решил попробовать отремонтировать. Обратился в этот сервисный центр и не пожалел. Профессионалы своего дела быстро восстановили мой телефон. Рекомендую посетить их сайт: ремонт телефонов и компьютеров.

  56. ремонт кондиционеров

    <a href=”https://remont-kondicionerov-wik.ru”>сервисный центр кондиционеров</a>

  58. Ремонт проекторов

    Профессиональный сервисный центр по ремонту фото техники от зеркальных до цифровых фотоаппаратов.
    Мы предлагаем: надежный сервис ремонта проекторов
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  59. Ремонт камер видео наблюдения в Москве

    Профессиональный сервисный центр по ремонту камер видео наблюдения по Москве.
    Мы предлагаем: ремонт камер наблюдения
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  60. ремонт бытовой техники в нижнем новгороде

    Профессиональный сервисный центр по ремонту бытовой техники с выездом на дом.
    Мы предлагаем: ремонт крупногабаритной техники в нижнем новгороде
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  61. ремонт бытовой техники в перми

    Профессиональный сервисный центр по ремонту бытовой техники с выездом на дом.
    Мы предлагаем: ремонт крупногабаритной техники в перми
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  65. ремонт техники в красноярске

    Профессиональный сервисный центр по ремонту бытовой техники с выездом на дом.
    Мы предлагаем: ремонт крупногабаритной техники в красноярске
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  71. ремонт бытовой техники в ростове на дону

    Профессиональный сервисный центр по ремонту бытовой техники с выездом на дом.
    Мы предлагаем:сервисные центры в ростове на дону
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  82. Ремонт посудомоечных машин в Москве

    Профессиональный сервисный центр по ремонту посудомоечных машин с выездом на дом в Москве.
    Мы предлагаем: ремонт посудомоечных машин
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  94. Психолог сейчас

    + В конфликте с родителями, общение холодное или его нет вовсе
    + На грани развода
    + Вечно в поиске себя, не знаете чем
    заниматься или боитесь идти в свою реализацию
    + В конфликте с родителями, общение холодное или его нет вовсе
    + Одиноки, нет друзей и сложно строить отношения
    с людьми
    + Делаете результаты через преодоление и страдания
    + Вечно в поиске себя, не знаете чем заниматься или боитесь идти в свою
    реализацию
    + Не можете построить долгие отношения, проще без них, партнёры всё время не те
    + Не можете построить долгие
    отношения, проще без них,
    партнёры всё время не те
    + Вечно в поиске себя, не знаете чем заниматься или боитесь идти в свою реализацию
    + Понимаете, что любовь к себе важна,
    но не знаете как это и считаете себя скорее умным человеком,
    чем красивым
    + Делаете результаты через преодоление и страдания
    + В конфликте с родителями, общение холодное или его нет вовсе
    + В конфликте с родителями, общение холодное или его нет вовсе
    + Тащите всё на себе, нет времени на
    жизнь
    https://t.me/s/psyholog_online_just_now

  99. сервис центры в волгограде

    Профессиональный сервисный центр по ремонту бытовой техники с выездом на дом.
    Мы предлагаем: ремонт крупногабаритной техники в волгограде
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  107. сервис центры в воронеже

    Профессиональный сервисный центр по ремонту бытовой техники с выездом на дом.
    Мы предлагаем: сервисные центры по ремонту техники в воронеже
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  109. Ремонт электросамокатов в Москве

    Профессиональный сервисный центр по ремонту электросамокатов в Москве.
    Мы предлагаем: сервис по ремонту электросамокатов
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  119. Индексация ссылок в Google

    Начните массовую индексацию ссылок в Google прямо cейчас!
    Быстрая индексация ссылок имеет ключевое значение для успеха вашего онлайн-бизнеса. Чем быстрее поисковые системы обнаружат и проиндексируют ваши ссылки, тем быстрее вы сможете привлечь новую аудиторию и повысить позиции вашего сайта в результатах поиска.
    Не теряйте времени! Начните пользоваться нашим сервисом для ускоренной индексации внешних ссылок в Google и Yandex. Зарегистрируйтесь сегодня и получите первые результаты уже завтра. Ваш успех в ваших руках!

  120. сервис центры в челябинске

    Профессиональный сервисный центр по ремонту бытовой техники с выездом на дом.
    Мы предлагаем: сервисные центры по ремонту техники в челябинске
    Наши мастера оперативно устранят неисправности вашего устройства в сервисе или с выездом на дом!

  135. ремонт телефонов москва

    Мой телефон перестал заряжаться, и я не знал, что делать. По совету друга обратился в этот сервисный центр. Мастера быстро нашли проблему и устранили её. Теперь мой телефон снова в строю! Рекомендую всем: сервисы ремонта телефонов.

发表评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注

Scroll to Top