当前位置: 首页 > news >正文

时间复杂度的计算

个人主页:平行线也会相交
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创
收录于专栏【数据结构初阶(C实现)】
在这里插入图片描述

文章目录

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

时间复杂度(就是一个函数)的计算,在算法中的基本操作的执行次数。就是算法的时间复杂度。

1

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);
}

Func1执行的基本操作次数:F(N)=N^2+2*N+10。Func1的时间复杂度就是O(N^2)

2

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);
}

Func2的时间复杂度是O(N)

3

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

Func3的时间复杂度是:O(M+N)

4

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

对于这种运行次数可以确定为常数次的时间复杂度就是O(1)

5

const char* strchr(const char* str, int character)
{while (*str){if (*str == character){return str;}str++;}
}

最好情况:1次找到。
最坏情况:N次找到。
平均情况:N/2次找到。

由于在实际算法种关注的是算法最坏情况的运行情况,所以说数组中搜索数据时间复杂度为O(N)

6

int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n - 1;while (begin <= end){int mid = begin + ((end - begin) >> 1);if (a[mid] > x){end = mid - 1;}else if (a[mid] < x){begin = mid + 1;}else{return mid;}}return -1;
}

二分查找就是用来查找你要查找的数据的,如果找到了,就返回所要查找数据的下标。
先来看一下最好情况O(1),即查找一次就找到了

看一下最坏情况log以2为底,N的对数
在这里插入图片描述
最好情况是1次很好理解,即把数据折半一次就找到了。
我们来看一下最坏的情况:我们首先要知道,查找一次,数据就要折半一次,查找一次,数据就要折半一次;所以当你一直查找,即一直折半直到折半到只有一个数据的时候,此时要么找到了,要么就没找到(没找到就是这些数据中根本就没有你所要查找的数据)。
比如:假设N是数组中元素的个数,x表示最坏情况的查找次数。查找一次就折半一次,即N/2,查找第二次:N/2/2;查找第三次:N/2/2/2,所以你要查找几次就需要除以几个2,直到最后查找到最后数组中只剩下一个元素的时候,即N/2/2/2/2……/2(除以x个2)=1;
把该式子整理一下就变成了这样:2^x=Nx=log以2为底N的对数。即:
在这里插入图片描述

7

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

时间复杂度是O(N),准确来说是O(N+1),只不过那个1忽略不计了。
在这里插入图片描述

8

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

在这里插入图片描述
但是这个算法很慢,当N是50的时候就要运行很长时间才行。
在这里插入图片描述
在这里插入图片描述

9

void BubbleSort(int* a, int n)
{assert(a);int i = 0;for (i = 0; i < n-1; i++){int j = 0;int count = 0;for (j = 0; j < n - 1 - i; j++){if (a[j] > a[j + 1]){int tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;count = 1;}}if (count == 0){break;}}
}

最好情况就是冒泡排序的第一趟就好了即O(N)
最坏情况:O(N^2)
在这里插入图片描述
好了,以上就是一些时间复杂度的一些计算,就到这里吧各位。
再见啦!!!
在这里插入图片描述

相关文章:

时间复杂度的计算

个人主页&#xff1a;平行线也会相交 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 平行线也会相交 原创 收录于专栏【数据结构初阶&#xff08;C实现&#xff09;】 文章目录123456789时间复杂度&#xff08;就是一个函数&#xff09;的计算&#xff0c;…...

站内信箱系统的设计与实现

技术&#xff1a;Java、JSP等摘要&#xff1a;在经济全球化和信息技术成为发展迅速的今时今日&#xff0c;人们通过电子邮件收发进行信息传递已经成为主流。随着互联网和网络办公的发展&#xff0c;电子邮件正在被广泛应用在人们的日常生活中。跟据调查研究统计&#xff0c;在全…...

systemV共享内存

systemV共享内存 共享内存区是最快的IPC形式。共享内存的大小一般是4KB的整数倍&#xff0c;因为系统分配共享内存是以4KB为单位的&#xff08;Page&#xff09;&#xff01;4KB也是划分内存块的基本单位。 之前学的管道&#xff0c;是通过文件系统来实现让不同的进程看到同一…...

Python基础之if逻辑判断

在学习if语句之前&#xff0c;我们先学习一种数据类型&#xff0c;布尔类型&#xff08;bool&#xff09;&#xff0c;在if语句中&#xff0c;我们需要通过判断条件是否为真或者假&#xff0c;才进入下面的语句块执行。 一、布尔类型&#xff08;bool&#xff09; 布尔类型&a…...

实现pdf文件预览

前言 工作上接到的一个任务&#xff0c;实现pdf的在线预览&#xff0c;其实uniapp中已经有对应的api&#xff1a;uni.openDocument(OBJECT)&#xff08;新开页面打开文档&#xff0c;支持格式&#xff1a;doc, xls, ppt, pdf, docx, xlsx, pptx。&#xff09;**实现了相关功能…...

【java】alibaba Fastjson --全解史上最快的JSON解析库

文章目录前序Fastjson 简介Fastjson 的优点速度快使用广泛测试完备使用简单功能完备下载和使用将 Java 对象转换为 JSON 格式JSONField创建 JSON 对象JSON 字符串转换为 Java 对象使用 ContextValueFilter 配置 JSON 转换使用 NameFilter 和 SerializeConfigFastjson 处理日期F…...

绝对零基础的C语言科班作业(期末模拟考试)(十道编程题)

编程题&#xff08;共10题&#xff1b; 共100.0分&#xff09;&#xff08;给猛男妙妙屋更一篇模拟考试&#xff09;模拟1&#xff08;输出m到n的素数&#xff09;从键盘输入两个整数[m,n], 输出m和n之间的所有素数。 输入样例&#xff1a;3&#xff0c;20输出样例&#xff1a;…...

按位与为零的三元组[掩码+异或的作用]

掩码异或的作用前言一、按位与为零的三元组二、统计分组1、map统计分组2、异或掩码总结参考资料前言 当a b 0时&#xff0c;我们能够很清楚的知道b是个什么值&#xff0c;b 0 - a -a&#xff0c;如果当a & b 0时&#xff0c;我们能够很清楚的知道b是什么值吗&#xf…...

C++基础篇(一)-- 简单入门

C 语言是在优化 C 语言的基础上为支持面向对象的程序设计而研制的一个通用目的的程序设计语言。在后来的持续研究中&#xff0c;C 增加了许多新概念&#xff0c;例如虚函数、重载、继承、标准模板库、异常处理、命名空间等。 C 语言的特点主要表现在两个方面&#xff1a;全面兼…...

前端整理 —— javascript 2

1. generator&#xff08;生成器&#xff09; 详细介绍 generator 介绍 generator 是 ES6 提供的一种异步编程解决方案&#xff0c;在语法上&#xff0c;可以把它理解为一个状态机&#xff0c;内部封装了多种状态。执行generator&#xff0c;会生成返回一个遍历器对象。返回的…...

Spring-注解注入

一、回顾XML注解 bean 配置 创建 bean public class Student { } 配置 xml bean <?xml version"1.0" encoding"UTF-8"?> <beans xmlns"http://www.springframework.org/schema/beans"xmlns:xsi"http://www.w3.org/2001/XMLSche…...

华为校招机试 - 攻城战(Java JS Python)

目录 题目描述 输入描述 输出描述 用例 题目解析 JavaScript算法源码 Java算法源码...

Docker入门

Docker一、何为DockerDocker是一个开源的应用容器引擎&#xff0c;基于GO语言并遵循从Apache2.0协议开源。Docker可以让开发者打包他们的应用以及依赖包到一个轻量级、可移植的容器中&#xff0c;然后在发布到任何流行的Linux机器上&#xff0c;也可以实现虚拟化。容器是完全使…...

时间序列分析 | CNN-LSTM卷积长短期记忆神经网络时间序列预测(Matlab完整程序)

时间序列分析 | CNN-LSTM卷积长短期记忆神经网络时间序列预测(Matlab完整程序) 目录 时间序列分析 | CNN-LSTM卷积长短期记忆神经网络时间序列预测(Matlab完整程序)预测结果模型输出基本介绍完整程序参考资料预测结果 模型输出 layers = 具有以下层的 151 Layer 数组:...

【蒸滴C】C语言结构体入门?看这一篇就够了

目录 一、结构体的定义 二、结构的声明 例子 三、 结构成员的类型 结构体变量的定义和初始化 1.声明类型的同时定义变量p1 2.直接定义结构体变量p2 3.初始化&#xff1a;定义变量的同时赋初值。 4.结构体变量的定义放在结构体的声明之后 5.结构体嵌套初始化 6.结构体…...

第十三届蓝桥杯

这里写目录标题一、刷题统计&#xff08;ceil函数返回的是等值于某最小整数的浮点值&#xff0c;不强制转换回int就wa&#xff0c;没错就连和int整数相加都wa二、修剪灌木&#xff08;主要应看清楚会调转方向三、统计子矩阵&#xff08;前缀和滑动窗口⭐&#xff09;四、[积木画…...

消息队列mq

应用场景&#xff1a; 1、解耦 2、削峰填谷 3、异步处理 4、消息通讯 工作模式&#xff1a; 一个消息只能被消费一次&#xff08;订阅模式除外&#xff09;&#xff0c;消费者接受到消息会回调业务逻辑&#xff0c;消费逻辑写在回调函数里面。 1、简单模式&#xff1a;一个生产…...

[学习笔记]黑马程序员Spark全套视频教程,4天spark3.2快速入门到精通,基于Python语言的spark教程

文章目录视频资料&#xff1a;一、Spark基础入门&#xff08;环境搭建、入门概念&#xff09;第二章&#xff1a;Spark环境搭建-Local2.1 课程服务器环境2.2 Local模式基本原理2.3 安装包下载2.4 Spark Local模式部署第三章&#xff1a;Spark环境搭建-StandAlone3.1 StandAlone…...

git push和 git pull的使用

git push与git pull是一对推送/拉取分支的git命令。git push 使用本地的对应分支来更新对应的远程分支。$ git push <远程主机名> <本地分支名>:<远程分支名>*注意: 命令中的本地分支是指将要被推送到远端的分支&#xff0c;而远程分支是指推送的目标分支&am…...

首发,pm3包,一个用于多组(3组)倾向评分匹配的R包

目前&#xff0c;本人写的第二个R包pm3包已经正式在CRAN上线&#xff0c;用于3组倾向评分匹配&#xff0c;只能3组不能多也不能少。 可以使用以下代码安装 install.packages("pm3")什么是倾向性评分匹配&#xff1f;倾向评分匹配&#xff08;Propensity Score Match…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...