【数据结构初阶】时间复杂度和空间复杂度详解

今天我们来详细讲讲时间复杂度和空间复杂度,途中如果有不懂的地方可翻阅我之前文章。

个人主页:小八哥向前冲~-CSDN博客

数据结构专栏:数据结构【c语言版】_小八哥向前冲~的博客-CSDN博客

c语言专栏:c语言_小八哥向前冲~的博客-CSDN博客

 在平常写代码时,碰见一个问题,有时候第一种思路代码量相对较多,而第二种思路代码量相对较小。这时候你可能会选择代码量较小的思路进行解答。但真的代码量越少,代码运行效率更快嘛?

那可不一定,有时候代码量大的反而更好,算法效率并不取决于代码量的,衡量一个算法或一个思路好不好,主要看的是时间复杂度和空间复杂度的

时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间

我们率先讲讲时间复杂度。

时间复杂度概念

我们先来看看它的定义:

在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一 个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知 道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个 分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。

也就是说:算法中基本操作的执行次数就是时间复杂度

我们来看个例子:

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

要计算它的时间复杂度,我们不妨计算count执行了多少次,显然执行了N*N+2*N+10次,到这里你不会就以为它的空间复杂度就是N*N+2*N+10了吧。那可就大错特错了!

实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这 里我们使用大O的渐进表示法

大o的渐进表示法

这里我们不妨看图:

不难看出F(N)的值主要取决于N*N,那么我们说这个算法的时间就是o(N*N),也就是说我们只取对这个算法影响最深的一项

也就是说大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。

但是有时候我们的算法会出现最好情况,最坏情况。什么意思呢?我们看个例子(二分查找):

 // 计算BinarySearch的时间复杂度?
int BinarySearch(int* a, int n, int x)
 {
    assert(a);
 
    int begin = 0;
    int end = n-1;
    // [begin, end]:begin和end是左闭右闭区间,因此有=号
    while (begin <= end)
    {
        int mid = begin + ((end-begin)>>1);
        if (a[mid] < x)
            begin = mid+1;
        else if (a[mid] > x)
            end = mid-1;
        else
            return mid;
    }
 
    return -1;
 }

这个例子的最坏情况:一次就找到。最坏情况:log2N次。为什么呢?我们分析一下:查找一次对半砍,两次对半砍两次,一直到砍到只剩最后一个值了或者最后一个值都不是要找的数,这就是最坏情况。

我们计算一下:

注意:如果有多种情况的话,我们一般算最坏情况。

我们来看看其他例子。

计算时间复杂度例题

冒泡排序例子

// 计算BubbleSort的时间复杂度?
void BubbleSort(int* a, int n)
 {
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i-1] > a[i])
            {
                Swap(&a[i-1], &a[i]);
                exchange = 1;
            }
        }
 
        if (exchange == 0)
            break;
    }
 }

我们来计算一下:N个数排序,第一次N-1趟冒泡,第二次N-2次冒泡,依次递减,其中每趟冒泡两两比较,我们不难算出N-1+N-2+N-3+N-4+........+1,也就是等差数列,我们算出为N*(N-1)/2,到这里是不是豁然开朗?最终为o(N*N)

常数例子

我们再来看一下另一个常数例子:

// 计算Func4的时间复杂度?
void Func4(int N)
 {
    int count = 0;
    for (int k = 0; k < 100; ++ k)
    {
        ++count;
    }
    printf("%d\n", count);
 }

我们不难看出执行了100次(非常准确),但不会你以为时间复杂度为o(100)吧?其实不然,确实执行行了100次,但因为是常数次,我们一律规定为o(1)。

注意:这里的o(1)并不是只执行了1次,而是代表执行了常数次!

递归例子

// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N)
 {
    if(0 == N)
        return 1;
    
    return Fac(N-1)*N;
 }

刚刚接触递归例子是不是有点摸不着头脑?别急!

我们知道当N为0时就停止,当N>0时就一直调用这个函数,调用多少次呢?调用到0就停止!不难算出调用了N次,时间复杂度也就是o(N)!

我们可以上图理解一下:

我们来看一个另一个典型例子----斐波拉及数列!

// 计算斐波那契递归Fib的时间复杂度?
long long Fib(size_t N)
 {
    if(N < 3)
        return 1;
    
    return Fib(N-1) + Fib(N-2);
 }

我们不难看出:

F(N)调用F(N-1)和F(N-2),F(N-1)调用F(N-2)和F(N-3)........直到调用到N<3就停止

既然这样仍然看不出执行次数,我们上图看看:

这样看是不是更加清楚呢?但是仍然存在一些瑕疵和疏漏:有些项并没有那么多项

我们再上图:

值得注意的是不影响算时间复杂度!

显然这个递归算法不实用!因为次数一旦大一点,计算机就算不出来(要耗费一点时间,不信可以自行试试!)

空间复杂度概念

空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度 。 空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法

注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定

一般理解了时间复杂度,空间的复杂度就手到擒来了!

我们来看一些例题感受一下!

计算空间复杂度例题

常数例子

一个最常见的常数例子就是冒泡排序了,我们来看看:

// 计算BubbleSort的空间复杂度?
void BubbleSort(int* a, int n)
 {
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i-1] > a[i])
            {
                Swap(&a[i-1], &a[i]);
                exchange = 1;
            }
        }
 
        if (exchange == 0)
            break;
    }
 }

不难看出:这个排序开辟了常数个额外空间,也就是o(1)

常见例子

long long* Fibonacci(size_t n)
 {
 if(n==0)
 return NULL;
 }
 long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
 fibArray[0] = 0;
 fibArray[1] = 1;
 for (int i = 2; i <= n ; ++i)
    {
 fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
    }
 return fibArray;

不难看出:开辟了n+1个额外空间,也就是o(N)

递归例子

// 计算阶乘递归Fac的空间复杂度?
long long Fac(size_t N)
 {
 if(N == 0)
 return 1;
 return Fac(N-1)*N;
 }

不难看出:递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N)

常见复杂度对比

算法有很多种,只要存在就有它的道理----存在即合理!只要我们理解它的底层逻辑,那么什么都不在话下!

好了,我们下期见!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/583205.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

网络服务SSH-远程访问及控制

一.SSH远程管理 1.SSH介绍 SSH&#xff08;Secure Shell&#xff09;是一种安全通道协议&#xff0c;最早是由芬兰的一家公司开发出来&#xff0c;并且在IETF &#xff08;Internet Engineering Task Force&#xff09;的网络草案基础上制定而成的标准协议。主要用来实现字符…

合规基线:让安全大检查更顺利

前言 说起安全检查&#xff0c;安全从业人员可能都非常熟悉“安全标准”概念。所有企事业单位网络安全建设都需要满足来自于国家或监管单位的安全标准&#xff0c;如等保2.0、CIS安全标准等。安全标准&#xff0c;还有一个叫法就是“安全基线”。字典上对“基线”的解释是&…

【PostgreSQL】pg触发器介绍

注: 本文为云贝教育 刘峰 原创&#xff0c;请尊重知识产权&#xff0c;转发请注明出处&#xff0c;不接受任何抄袭、演绎和未经注明出处的转载。 触发器是在对指定表执行指定更改操作&#xff08;SQL INSERT、UPDATE、DELETE 或 TRUNCATE 语句&#xff09;时自动运行的一组操作…

Java全栈开发前端+后端(全栈工程师进阶之路)-环境搭建

在课程开始前我们要配置好我们的开发环境&#xff0c;这里我的电脑太乱了&#xff0c;我使用vm虚拟机进行搭建开发环境&#xff0c;如果有需要环境的或者安装包&#xff0c;可以私信我。 那我们开始 首先我们安装数据库 这里我们使用小皮面板 小皮面板(phpstudy) - 让天下没…

面向表格数据的大模型推理

现实世界中存在大量未利用的先验知识和未标记数据。而在医疗等高价值领域&#xff0c;获取足够标记数据训练机器学习模型尤其困难&#xff0c;这限制了传统监督学习算法的应用。尽管深度学习方法在其他领域取得了显著进展&#xff0c;但在表格数据分类上仍未能超越传统的机器学…

WEB攻防-PHP特性-函数缺陷对比

目录 和 MD5函数 intval ​strpos in_array preg_match str_replace 和 使用 时&#xff0c;如果两个比较的操作数类型不同&#xff0c;PHP 会尝试将它们转换为相同的类型&#xff0c;然后再进行比较。 使用 进行比较时&#xff0c;不仅比较值&#xff0c;还比较变量…

在Linux操作系统中关于磁盘(硬盘)管理的操作

电脑中数据存储设备&#xff1a;硬盘&#xff08;实现数据的持久化存储&#xff09;&#xff0c;内存 在Linux操作系统中一切皆文件的思想&#xff0c;所有的设备在Linux操作系统中都是通过文件来标识的&#xff0c;所以每一个硬盘都对应一个块设备文件。 在Linux操作系统中所…

虚函数表与虚函数表指针

虚函数表与虚函数表是用来实现多态的&#xff0c;每一个类只有一个虚函数表 静态多态&#xff1a;函数重载&#xff08;编译期确定&#xff09; 动态多态&#xff1a;虚函数&#xff08;运行期确定&#xff09; 虚函数表的创建时机&#xff1a; 生成时间&#xff1a; 编译期…

C++——map和set的基础应用

目录 1.关联式容器 2.键值对 3.树型结构的关联式容器 4.set&#xff08;key模型&#xff09; 1.set性质 2.注意 3.set的使用 1.创建对象 2.插入 3.删除 4.查找 4.map&#xff08;key value模型&#xff09; 1.性质 2.map的使用 1.创建对象 2.插入 3.删除 4.[] 1.关联式容器 C中…

pytho爬取南京房源成交价信息并导入到excel

# encoding: utf-8 # File_name: import requests from bs4 import BeautifulSoup import xlrd #导入xlrd库 import pandas as pd import openpyxl# 定义函数来获取南京最新的二手房房子成交价 def get_nanjing_latest_second_hand_prices():cookies {select_city: 320100,li…

C语言 | Leetcode C语言题解之第50题Pow(x,n)

题目&#xff1a; 题解&#xff1a; double myPow(double x, int n){if(n 0 || x 1){return 1;}if(n < 0){return 1/(x*myPow(x,-(n1)));}if(n % 2 0){return myPow(x*x,n/2);}else{return x*myPow(x*x,(n - 1)/2);} }

selenium 4.x入门篇(环境搭建、八大元素定位)

背景 Web自动化测现状 1. 属于 E2E 测试 2. 过去通过点点点 3. 好的测试&#xff0c;还需要记录、调试网页的细节 一、selenium4.x环境搭建 一键搭建 pip3 install webdriver-helper 安装后自动的完成&#xff1a; 1. 查看浏览器的版本号 2. 查询操作系统的类型…

68.网络游戏逆向分析与漏洞攻防-利用数据包构建角色信息-自动生成CPP函数解决数据更新的问题

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 如果看不懂、不知道现在做的什么&#xff0c;那就跟着做完看效果&#xff0c;代码看不懂是正常的&#xff0c;只要会抄就行&#xff0c;抄着抄着就能懂了 内容…

0426GoodsBiddingAJAX项目

0426GoodsBiddingAJAX项目包-CSDN博客 数据库字段 ​ 管理员的登录界面 ​ 登录成功跳转在线拍卖界面&#xff0c;使用监听器拦截请求&#xff0c;只能登录管理员后访问该界面 ​ 商品竞拍列表 ​ 商品竞拍列表的竞拍操作&#xff1a; ​ 1 用户未登录跳转用户登录界面&#x…

(三十一)第 5 章 数组和广义表(稀疏矩阵的三元组行逻辑链接的顺序存储表示实现)

1. 背景说明 2. 示例代码 1)errorRecord.h // 记录错误宏定义头文件#ifndef ERROR_RECORD_H #define ERROR_RECORD_H#include <stdio.h> #include <string.h> #include <stdint.h>// 从文件路径中提取文件名 #define FILE_NAME(X) strrchr(X, \\) ? strrch…

算法03贪心与动态规划

算法03贪心与动态规划 1. 贪心与动态规划概述1.贪心1.1贪心概述1.2贪心常用场景1.3贪心解题思路 2.动态规划2.1动态规划概述2.2动态规划常用场景2.3动态规划解题模板 3.浅谈贪心与动态规划的关系 2.贪心经典题目区间问题 3.动态规划经典题目3.1体会“从整体到局部”的思考过程3…

2024Mac系统热门游戏排行榜 Mac支持的网络游戏有哪些?mac能玩哪些大型网游 苹果电脑Mac游戏资源推荐 Mac玩Windows游戏

“游戏是这个世界上唯一能和女性争夺男朋友的东西&#xff08;/滑稽&#xff0c;有不少女生也喜欢玩游戏&#xff09;。” 虽然只是一句玩笑话&#xff0c;不过也可以看出游戏对大多数男生来说是必不可少的一项娱乐活动了。而网络游戏是游戏中的一大分支&#xff0c;能让玩家们…

zabbix自动发现和自动注册

一、zabbix自动发现 1.1 确保客户端上的zabbix-agent2服务器状态正常 1.2 在web页面删除原有的客户端主机 1.3 在服务端和客户端上配置hosts 1.4 web端配置自动发现 二、zabbix自动注册 2.1 环境配置 2.2 修改zabbix-agent2配置文件 过滤非#或非&#xffe5;开头的内容 2.3 we…

基于遗传优化算法的TSP问题求解matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 5.完整程序 1.程序功能描述 基于遗传优化算法的TSP问题求解&#xff0c;分别对四个不同的城市坐标进行路径搜索。 2.测试软件版本以及运行结果展示 MATLAB2022A版本运行 3.核心程序 ....…

前端开发攻略---用原生JS在网页中也能实现语音识别

1、语音识别的过程 语音识别涉及三个过程&#xff1a;首先&#xff0c;需要设备的麦克风接收这段语音&#xff1b;其次&#xff0c;语音识别服务器会根据一系列语法 (基本上&#xff0c;语法是你希望在具体的应用中能够识别出来的词汇) 来检查这段语音&#xff1b;最后&#xf…