【数据结构】复杂度学习

简介: 【数据结构】复杂度学习


一,关于时间复杂度与空间复杂度

  算法效率的度量是通过时间复杂度和空间复杂度来进行描述的,时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。但我们在题目中判定一个程序是否优秀时,却很少看到用空间复杂度来判定,这是为什么呢?

  空间复杂度与之相关的部件是内存,那我们思考一个问题,如果我们所拥有的内存大小让我们不必在使用他时担心它够不够用,那空间复杂度是不是就不那么重要了呢?答案是肯定的。接下来我为各位看官介绍摩尔定律,相信大家心里的疑惑就能消除许多。大家请看:

  摩尔定律是英特尔创始人之一戈登·摩尔的经验之谈,其核心内容为:集成电路上可以容纳的晶体管数目在大约每经过18个月到24个月便会增加一倍。换言之,处理器的性能大约每两年翻一倍,同时价格下降为之前的一半。

  摩尔定律是内行人摩尔的经验之谈,汉译名为“定律”,但并非自然科学定律,它一定程度揭示了信息技术进步的速度。

  所以我们在学习过程中重点掌握时间复杂度,因为时间复杂度跟CPU挂钩,决定了算法执行的时间,但是CPU的发展已经接近瓶颈,所以现在的厂商致力于增加CPU的核心数,并且在平常使用中,运行速度在人们心中更为重要。

二,时间复杂度如何衡量?

  时间复杂度如何衡量呢?在一个程序的开头和结尾各放置两个计时器,运行结束后将得到的两数相减所得的值,不就可以用来和其他的程序比较吗?这固然是一个方法,直观还容易比较。但是,比较的两个机器的硬件可能是不同的,一个CPU为8核2核的机器运行一个相同的代码,按照上面的这种判定方式,他两的时间一定相同吗?答案显而易见。那么该如何比较呢?我们使用大O渐进表示法,下来向大家介绍这种方法:

三,大O渐进表示法

1. 大O渐进表示法如何计算时间复杂度:

  我们先来看一看时间复杂度的定义:

  在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。来自于百度百科

  从中我们可以知道,**时间复杂度是一个函数,但是不包括这个函数的低阶项和首项系数。**前者我们可以通过下面给出的例子容易知道,后者我们之后介绍。

定义:大O符号是用于描述函数渐进性为的数学符号。

  计算复杂度时我们计算的是通过计算算法中的基本操作的执行次数,来侧面对运行时间进行估算。

大O渐进法的使用方法:

① 用 常数1 取代运行时间中的所有加法常数。

② 在修改后的运行次数函数中,只保留最高阶项。

③ 如果最高阶存在且不是1 ,则去除与这个项目相乘的常数。最后得到的结果就是大O阶。

2.先向大家举一个计算的例子

  请问这串代码的时间复杂度是多少?

void Func2(int N){
  int count =0;
  for (int k = e ; k < 2 * N ; ++ k){
    ++count;
  }
  int M= 10;
  while(M--){
    ++count;
  }
  printf("%d\n",count)
}

根据代码我们可以得出 :

F ( N ) = 2 ∗ N + 10 ; F(N) = 2 * N + 10;F(N)=2N+10;

得到他的时间复杂度为O(N).

从公示我们可以看到,时间复杂度实际上就是一个函数

那为什么2 * N + 10 会的得到时间复杂度为O(N)。

之后会更新O(1),O(N),O(2 N 2^N2N)等不同情况下的复杂度如何计算

相关文章
|
2月前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
68 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
2月前
|
算法 Java 数据库
数据结构与算法学习十五:哈希表
这篇文章详细介绍了哈希表的概念、应用实例、实现思路,并提供了使用Java实现的哈希表代码。
66 0
数据结构与算法学习十五:哈希表
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】