C语言【数据结构】:时间复杂度和空间复杂度.详解

引言

        详细介绍什么是时间复杂度和空间复杂度。

前言:为什么要学习时间复杂度和空间复杂度

        算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。

        时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量⼀个算法运行所需要的额外空间。 在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。

一、时间复杂度 

问:时间复杂度是程序运行的时间吗?                     

        这是一个很严重的问题。这里先肯定回答:不是

仔细往下看,最后你亲自来回答这个问题                                

1.什么是时间复杂度

        时间复杂度是对一个算法运行时间长短的一种度量它描述的是随着输入数据规模 n 的增大,算法执行时间的增长趋势,而不是具体的运行时间。因为具体运行时间会受到硬件、编程语言、编译器等多种因素的影响,所以使用时间复杂度可以更客观地评估算法的效率。

    

程序执行的时间  =  二进制指令运行的时间 * 执行的次数 

        因为程序在计算机中二进制指令的运行时间是非常快的,可以假定时间是一样的,所以使用代码的执行次数来等效程序的执行时间 

2.表示方法(大O表示法)

        通常使用大 O 符号(Big O notation)来表示时间复杂度。大 O 符号表示的是算法执行时间的上界,即最坏情况下的时间复杂度。看到这里你可能不知道什么是大O表示法,跟随下面的案例来理解,就明白什么是大O表示法了。

        推导大O阶规则

        1. 时间复杂度函数式 T(N) 中,只保留最高阶项,去掉那些低阶项,因为当 N 不断变⼤时, 低阶项对结果影响越来越⼩,当 N 无穷大时,就可以忽略不计了。

         2. 如果最高阶项存在且不是 1 ,则去除这个项目的常数系数,因为当 N 不断变大,这个系数对结果影响越来越小,当 N 无穷大时,就可以忽略不计了。

         3.T(N) 中如果没有 N 相关的项目,只有常数项,用常数 1 取代所有加法常数。

3.常见的时间复杂度

1. O(1):常数时间复杂度

代码一:

        推导一下这段代码的执行次数T与n之间的函数关系


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

        T(N)= 2 * N + 10;

当N足够大时,从1 增长到10000000,会发现2 和10 对次数的影响不是很大,所以

        1. 如果最高阶项存在且不是 1 ,则去除这个项目的常数系数,因为当 N 不断变大,这个系数对结果影响越来越小,当 N 无穷大时,就可以忽略不计了。

        2. T(N) 中如果没有 N 相关的项目,只有常数项,用常数 1 取代所有加法常数。

代码二: 

void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}

        观察这段代码,会发现n和程序的执行次数是没有关系的(T(N)= 100),这时就认为时间复杂度为O(1);

2. O(n):线性时间复杂度

代码一:

        算法的执行时间与输入数据规模 n 成正比。

#include <stdio.h>// 计算数组元素的和
int sum(int arr[], int n) {int total = 0;for (int i = 0; i < n; i++) {total += arr[i];}return total;
}int main() {int arr[] = {1, 2, 3, 4, 5};int n = sizeof(arr) / sizeof(arr[0]);int result = sum(arr, n);printf("Sum = %d\n", result);return 0;
}

        在 sum 函数中,需要遍历数组中的每个元素,因此循环的执行次数与数组的长度 n 成正比,时间复杂度为 O(n)。即因为是要循环n次,所以是O(n)。

代码二: 

const char* strchr(const char* str, int character)
{const char* p_begin = 's';while (*p_begin != character){if (*p_begin == '\0')return NULL;p_begin++;}return p_begin;

 strchr执行的基本操作次数:

1)若要查找的字符在字符串第⼀个位置,则: T(N) = 1

2)若要查找的字符在字符串最后的⼀个位置, 则: T(N) = N

3)若要查找的字符在字符串中间位置,则:N T(N) = 2 因此:strchr的时间复杂度分为: 最好情况: O(1)

最坏情况: O(N)

平均情况: O(N)



通过上面我们会发现,有些算法的时间复杂度存在最好、平均和最坏情况。

最坏情况:任意输入规模的最大运行次数(上界)

平均情况:任意输入规模的期望运行次数

最好情况:任意输入规模的最小运行次数(下界)

大O的渐进表示法在实际中⼀般情况关注的是算法的上界,也就是最坏运行情况。


所以上面这段代码的时间复杂度是O(N)

3. O(n^2):平方时间复杂度

        算法的执行时间与输入数据规模 n 的平方成正比。

参考代码:
#include <stdio.h>// 冒泡排序
void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);bubbleSort(arr, n);for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

粗略理解:在 bubbleSort 函数中,使用了两层嵌套循环,因此时间复杂度为 O(n^2)。

细节分析:

        1)若数组有序,则: T(N)=N

        2)若数组有序且为降序,则: T(N)=  1 + 2 + 3 + .......+ n - 1 = ((n - 1) * (1 + n - 1) ) / 2   即等差数列求和公式:a1 = 1, an = n - 1, 共n - 1项。

        T(N)= (n^2) * 1 / 2 + n / 2;

       因此:BubbleSort的时间复杂度取最差情况为: O(N ^ 2)

4. O(log n ):复杂度

参考代码:
void func5(int n)
{int cnt = 1;while (cnt < n){cnt *= 2;}
}

当n= 2 时,执行次数为1

当n= 4 时,执行次数为2

当n=16时,执行次数为4

假设执行次数为x,则 2^x = x  因此执行次数: x=logn

因此:func5的时间复杂度取最差情况为:O(log n) 

这里为什么不写

因为这个在输入法上不好打出来

注意:在有的地方会把  logn  写成lgn,严格上来说这个是不对的

        当n接近无穷大时,底数的大小对结果影响不大。因此,一般情况下不管底数是多少都可以省略不写。

还有其他的时间复杂度如:n*logn, n!(n的阶乘),在以后的学习中肯定会遇到

二、空间复杂度

 1.什么是空间复杂度

定义

        空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一种度量,它描述的是随着输入数据规模 n 的增大,算法所需额外存储空间增长趋势。

注意:函数栈帧的创建和销毁是不算入空间复杂度的,即 创建函数 和 销毁函数 是不算入时间复杂度的。

表示方法

        同样使用大 O 符号来表示空间复杂度。

常见的空间复杂度及其示例代码

1. O(1):常数空间复杂度

算法在运行过程中所需的额外存储空间是固定的,不随输入数据规模 n 的变化而变化。

#include <stdio.h>// 计算数组元素的和
int sum(int arr[], int n) {int total = 0;for (int i = 0; i < n; i++) {total += arr[i];}return total;
}int main() {int arr[] = {1, 2, 3, 4, 5};int n = sizeof(arr) / sizeof(arr[0]);int result = sum(arr, n);printf("Sum = %d\n", result);return 0;
}

        在 sum 函数中,只使用了一个额外的变量 total 来存储数组元素的和,因此空间复杂度为 O(1)。

2. O(n):线性空间复杂度

算法在运行过程中所需的额外存储空间与输入数据规模 n 成正比。

#include <stdio.h>
#include <stdlib.h>// 复制数组
int* copyArray(int arr[], int n) {int *newArr = (int*)malloc(n * sizeof(int));for (int i = 0; i < n; i++) {newArr[i] = arr[i];}return newArr;
}int main() {int arr[] = {1, 2, 3, 4, 5};int n = sizeof(arr) / sizeof(arr[0]);int *newArr = copyArray(arr, n);for (int i = 0; i < n; i++) {printf("%d ", newArr[i]);}printf("\n");free(newArr);return 0;
}

在copyArray 函数中,使用了 malloc 函数动态分配了一个大小为 n 的数组,因此空间复杂度为 O(n)。 

5. 常见复杂度对比

  

       在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。

        但是,在算法竞赛中,往往需要有一种思想:用时间换空间,或者用空间换时间。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Matlab 基于专家pid控制的时滞系统

1、内容简介 Matlab 185-基于专家pid控制的时滞系统 可以交流、咨询、答疑 2、内容说明 略 在处理时滞系统&#xff08;Time Delay Systems&#xff09;时&#xff0c;使用传统的PID控制可能会面临挑战&#xff0c;因为时滞会导致系统的不稳定或性能下降。专家PID控制通过结…

MyBatis源码分析のSql执行流程

文章目录 前言一、准备工作1.1、newExecutor 二、执行Sql2.1、getMappedStatement2.2、query 三、Cache装饰器的执行时机四、补充总结 前言 本篇主要介绍MyBatis解析配置文件完成后&#xff0c;执行sql的相关逻辑&#xff1a; public class Main {public static void main(Str…

【MySQL】数据库基础

目录 一、什么是数据库1.1 为什么要有数据库1.2 数据库的本质是什么1.3 在Linux下看一下数据库 二、主流数据库三、基本使用3.1 连接服务器3.2 服务器&#xff0c;数据库&#xff0c;表关系 四、MySQL架构五、SQL分类六、存储引擎6.1 存储引擎是什么6.2 查看存储引擎6.3 存储引…

算是解决可以访问github但无法clone的问题

本文的前提是使用了**且可以正常访问github 查看代理的端口 将其配置到git 首先查看git配置 git config --list然后添加配置&#xff0c;我这边使用的是Hiddfy默认的端口是12334&#xff0c;如果是clash应该是7890 git config --global http.proxy 127.0.0.1:12334其他 删除…

SpringBoot第三站:配置嵌入式服务器使用外置的Servlet容器

目录 1. 配置嵌入式服务器 1.1 如何定制和修改Servlet容器的相关配置 1.server.port8080 2. server.context-path/tx 3. server.tomcat.uri-encodingUTF-8 1.2 注册Servlet三大组件【Servlet&#xff0c;Filter&#xff0c;Listener】 1. servlet 2. filter 3. 监听器…

AdaLoRA 参数 配置:CAUSAL_LM“ 表示因果语言模型任务

AdaLoRA 参数 配置:CAUSAL_LM" 表示因果语言模型任务 config = AdaLoraConfig( init_r=16, # 增加 LoRA 矩阵的初始秩 lora_alpha=32, target_modules=[“q_proj”, “v_proj”], lora_dropout=0.1, bias=“none”, task_type=“CAUSAL_LM” ) 整体功能概述 AdaLoraCon…

IP 协议

文章目录 IP 协议概述数据包格式首部校验和实例分析实例一 分片抓包分析参考 本文为笔者学习以太网对网上资料归纳整理所做的笔记&#xff0c;文末均附有参考链接&#xff0c;如侵权&#xff0c;请联系删除。 IP 协议 概述 IP 协议是 TCP/IP 协议簇中的核心协议&#xff0c;也…

日常开发记录-radioGroup组件

日常开发记录-radioGroup组件 1.前提2.问题&#xff1a;无限循环调用3.解释Vue 事件传播机制分析与无限循环原因解释4.解决 1.前提 在上一章的&#xff0c;我们实现了radio组件。从这进入了解 新增个radioGroup组件呢。 <template><divclass"q-radio-group&quo…

API调用comfyui工作流,做一个自己的app,chatgpt给我写的前端,一键创建自己的卡通形象,附源码

前言 工具介绍 首先 comfyui你是少不了的&#xff0c;这个是工作流的后端支持&#xff0c;用这个去调试工作流和生成API可调用文件 前端我们就用很流行的gradio吧&#xff0c;什么你一时半会没有学gradio的计划&#xff0c;没事&#xff0c;笔者也没系统学过&#xff0c;我干…

【网络】数据流(Data Workflow)Routes(路由)、Controllers(控制器)、Models(模型) 和 Middleware(中间件)

在图片中&#xff0c;数据流&#xff08;Data Workflow&#xff09;描述了应用程序中数据的流动过程&#xff0c;涉及 Routes&#xff08;路由&#xff09;、Controllers&#xff08;控制器&#xff09;、Models&#xff08;模型&#xff09; 和 Middleware&#xff08;中间件&…

【通义千问】蓝耘智算 | 智启未来:蓝耘MaaS×通义QwQ-32B引领AI开发生产力

【作者主页】Francek Chen 【专栏介绍】 ⌈ ⌈ ⌈人工智能与大模型应用 ⌋ ⌋ ⌋ 人工智能&#xff08;AI&#xff09;通过算法模拟人类智能&#xff0c;利用机器学习、深度学习等技术驱动医疗、金融等领域的智能化。大模型是千亿参数的深度神经网络&#xff08;如ChatGPT&…

Scratch 3.0安装包,支持Win7/10/11、Mac电脑手机平板、少儿便编程的启蒙软件。

Scratch是一款由麻省理工学院&#xff08;MIT&#xff09; 设计开发的少儿编程工具。其特点是&#xff1a;使用者可以不认识英文单词&#xff0c;也可以不使用键盘&#xff0c;就可以进行编程。构成程序的命令和参数通过积木形状的模块来实现。用鼠标拖动指令模块到脚本区就可以…

Deepseek学习--工具篇之Ollama

Deepseek学习--工具篇之Ollama 用途特点简化部署‌轻量级与可扩展性‌API支持‌预构建模型库‌模型导入与定制‌跨平台支持‌命令行工具与环境变量‌ 来源缘起诞生爆发持续 安装使用方法下载安装安装模型调用API 用途 我们在进行Deepseek本地部署的时候&#xff0c;通常会用到…

Flask多参数模版使用

需要建立目录templates&#xff1b; 把建好的html文件放到templates目录里面&#xff1b; 约定好参数名字&#xff0c;单个名字可以直接使用&#xff1b;多参数使用字典传递&#xff1b; 样例&#xff1a; from flask import render_template # 模板 (Templates) #Flask 使用…

LabVIEW旋转设备状态在线监测系统

为了提高大型旋转设备如电机和水泵的监控效率和故障诊断能力&#xff0c;用LabVIEW软件开发了一套实时监测与故障诊断系统。该系统集成了趋势分析、振动数据处理等多项功能&#xff0c;可实时分析电机电流、压力、温度及振动数据&#xff0c;以早期识别和预报故障。 ​ 项目背…

汽车PKE无钥匙进入系统一键启动系统定义与原理

汽车智能钥匙&#xff08;PKE无钥匙进入系统&#xff09;一键启动介绍 系统定义与原理 汽车无钥匙进入系统&#xff0c;简称PKE&#xff08;Passive Keyless Entry&#xff09;&#xff0c;该系统采用了RFID无线射频技术和车辆身份编码识别系统&#xff0c;率先应用小型化、小…

【Idea】 xml 文本粘贴保持原有文本的缩进格式

Idea xml 文本粘贴保持原有文本的缩进格式 在使用 IntelliJ IDEA 2018 版本中的 MyBatis 时&#xff0c;粘贴 SQL 语句会自动对齐&#xff0c;此时需要进行相关设置来禁用此功能。 setting——>Editor——>Code Style——>XML 勾选“Keep white spaces”

Unity 和 Python 的连接(通过SocketIO)附源码

在游戏或者项目开发中&#xff0c;Unity 通常用于创建前端&#xff0c;而 Python 则因其强大的数据处理能力常被用作后端。通过 Socket.IO&#xff0c;我们可以轻松地实现 Unity 和 Python 的实时通信。本文将介绍如何通过 Socket.IO 连接 Unity 和 Python&#xff0c;并附上完…

[IP]UART

UART 是一个简易串口ip&#xff0c;用户及配置接口简单。 波特率从9600至2000000。 该 IP 支持以下特性&#xff1a; 异步串行通信&#xff1a;标准 UART 协议&#xff08;1 起始位&#xff0c;8 数据位&#xff0c;1 停止位&#xff0c;无奇偶校验&#xff09;。 参数化配置…

vue2实现可拖拽菜单栏,及根据菜单内容自动扩展宽度

分为两个功能 基本的html: <el-scrollbarid"leftmenu"v-resize"MuneResize"wrap-class"scrollbar-wrapper"><el-menu:default-active"activeMenu":collapse"isCollapse":background-color"variables.menuBg&…