数据结构之算法的时间复杂度
1.时间复杂度的定义
在计算机科学中,算法的时间复杂度是一个函数,它定量描述了算法的运行时间。一个算法所花费的时间与其中语句的执行次数成正比列,算法中的基本操作的执行次数,为算法的时间复杂度
例1:
计算Func1中++count执行的次数
void Func1(int N)
{int count = 0;for(int i = 0; i < N; ++i){for(int j = 0; j < N; ++j){++count;}}for(int i = 0; i < 2 * N; ++i){++count;}int M = 10;while(M--){++count; }printf("%d\n", count);
}
Func1的基本操作次数:F(N) = N^2 + 2 * N + 10来分析一下是为什么?
首先可以看到这段代码有三个循环
第一个是由两个for内外嵌套组成:每次循环N次,执行了N次,即N + N + N.....=N * N = N^2 次
第二个循环执行了 2*N 次
第三个循环执行了 10 次
如果每个时间复杂度都要这么表示的话那太复杂了,所以我们只取最大量级来表示这段代码的时间复杂度
当N = 10时:F(N) = 130
当N = 20时:F(N) = 10210
当N = 30时:F(N) = 1002010
当我们的N取无穷大时 2 * N + 10这两个项对结果的影响已经不大了可以忽略不计,所以说只需要取N^2来表示它的时间复杂度就可以了
所以这段代码Func1的时间复杂度为: O(N ^ 2)
2.大O的渐进表示法
大O符号(Big O notation):是用于描述函数渐进行为的数学符号
推导大O阶方法:
(1).用常数1来取代运行时间中的所有加法常数
(2).在修改后的运行次数的函数中,只保留最高阶项
(3).如果最高阶存在且不是1,则去除与这个项目相乘的常数,得到的结果就是大O阶
通过上面一个例子我们可以发现大O渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数
我们来计算几道代码的时间复杂度
例1:
void Func2(int N)
{int count = 0;for(int i = 0; i < 2 * N; i++){++count;}int M = 10;while(M--){++count; }printf("%d", count);
}
F(N) = 2 * N +10
去掉与最高阶相乘的常熟和10使用大O渐进法表示法该段代码的时间复杂度为:O(N)
例2:
void Func3(int M, int N)
{int count = 0;for(int i = 0; i < M; i++){++count;}for(int j = 0; j < N; j++){++count;}printf("%d\n", count);
}
使用大O渐进法表示法该段代码的时间复杂度为:O(N + M)
因为M和N是未知的所以不能去掉它们两个任意一个
如果N大于M,则可以去掉M,反之可以去掉N,相等可任取M和N中任何一个
例3:
void Func4(int N)
{int count = 0;for(i = 0; i < 100: i++){++count;}printf("%d\n", count);
}
F(N) = 100
执行了100次,但是我们用1来表示
使用大O渐进法表示法该段代码的时间复杂度为:O(1)
注:这里的1表示代表1次,而是常数次
3.时间复杂度的最好,最坏和平均情况
另外有些算法的时间复杂度存在最好,平均,最坏情况:
最坏情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最好情况:任意输入规模最小运行次数(下界)
例4:
char* strchr(const char * str, int character)
{while(*Str){if(*str == character){return str;}str++;}return NULL;
}
例如:在一个长度为N的数组中找一个数据x
最好情况:1次找到
平均情况:N/2次找到
最坏情况:N次找到
在实际情况中一般关注的是算法的最坏运行情况,所以该段代码的时间复杂度为:O(N)
例5:
void BubbleSort(int *a, int n)
{assert(a);for(int end = n; end > 1; --end){for(int i = 1; i < end; i++){if(a[i - 1] > a[i]){int tmp = a[i];a[i] = a[i + 1];a[i + 1] = tmp;}}}
}
最好情况:O(N)
最坏情况将两个for循环跑满
外循环为n时,内循环循环n - 1次 然后按顺序n - 2, n-3, ....., 3, 2, 1通过判断可以知道这是一个等差数列,所以它的总和就为:n(n - 1 + 1)/2 = n^2*1/2 即最坏情况:O(N^2)
使用大O渐进法表示法去掉常数该段代码的时间复杂度为:O(N^2)
例6:
在数组有序的情况下:可以使用二分法(折半查找)
int binarysearch(int *a,int n, int x)
{int begin = 0;int end = n - 1;while(begin <= end){int mid = begin + ((end - begin)>>1);if(a[mid] > x){end = a[mid] - 1;}else if(a[mid] < x){begin = a[mid] + 1;}else{return mid;}}return -1;
}
最好情况:O(1)
最坏情况:区间缩放到一个值,要么找到,要么找不到,假设N为数组个数,x是最坏查找次数N每次除2就等于查找一次,折半查找多少次就除多少个2
N/2/2/2..../2 = 1, 因为n为int所以最小二分到1,2^x = N 即:x = logN(log在时间复杂度中表示以2为底)所以最坏情况:O(logN)
例7:
long long fac(size_t N)
{if(N == 0)return 1;elsereturn fac(N - 1) * N;
}
使用大O渐进法表示法该段代码的时间复杂度为:O(N)
例8:
long long Fib(int n)
{if(n < 3){return 1;}else{return Fib(n - 1) + Fib(n - 2);}
}
最好情况:O(1)
可以观察到该递归的方式为等差数列我们用求和公式可以得出:2^(N-1)-1
最坏情况用大O渐进表示法:O(2^N)
总结以上时间复杂度:O(1)>O(logN)>O(N)>O(N^2)>O(N^3)>O(2*N)
相关文章:

数据结构之算法的时间复杂度
1.时间复杂度的定义 在计算机科学中,算法的时间复杂度是一个函数,它定量描述了算法的运行时间。一个算法所花费的时间与其中语句的执行次数成正比列,算法中的基本操作的执行次数,为算法的时间复杂度 例1: 计算Func1…...
unity中物体被激活自动执行挂载代码
在Unity中,如果希望当物体被激活时自动执行特定的函数,可以利用 MonoBehaviour 的生命周期函数 OnEnable()。这个方法会在对象被激活时调用,可以用来执行初始化或者处理其他逻辑。以下是如何在脚本中使用 OnEnable() 方法: using UnityEngine;public class ActivateFuncti…...

Pandas数据可视化详解:大案例解析(第27天)
系列文章目录 Pandas数据可视化解决不显示中文和负号问题matplotlib数据可视化seaborn数据可视化pyecharts数据可视化优衣库数据分析案例 文章目录 系列文章目录前言1. Pandas数据可视化1.1 案例解析:代码实现 2. 解决不显示中文和负号问题3. matplotlib数据可视化…...

Redis基础教程(七):redis列表(List)
💝💝💝首先,欢迎各位来到我的博客,很高兴能够在这里和您见面!希望您在这里不仅可以有所收获,同时也能感受到一份轻松欢乐的氛围,祝你生活愉快! 💝Ὁ…...

鸿蒙开发:Universal Keystore Kit(密钥管理服务)【生成密钥(C/C++)】
生成密钥(C/C) 以生成ECC密钥为例,生成随机密钥。具体的场景介绍及支持的算法规格。 注意: 密钥别名中禁止包含个人数据等敏感信息。 开发前请熟悉鸿蒙开发指导文档:gitee.com/li-shizhen-skin/harmony-os/blob/master/README.md点击或者复…...

ssm“落雪”动漫网站-计算机毕业设计源码81664
目 录 摘要 1 绪论 1.1 研究背景 1.2 研究意义 1.3论文结构与章节安排 2系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1 数据新增流程 3.2.2 数据删除流程 2.3 系统功能分析 2.3.1 功能性分析 2.3.2 非功能性分析 2.4 系统用例分析 2.5本章小结 3 系统总体设…...
【面试题】Reactor模型
Reactor模型 定义 Reactor模型是一种事件驱动的设计模式,用于处理服务请求。它通过将事件处理逻辑与事件分发机制解耦,实现高性能、可扩展的并发处理。Reactor模型适用于高并发、事件驱动的程序设计,如网络服务器等。 特点 事件驱动&#…...

RedHat9 | kickstart无人值守批量安装
一、知识补充 kickstart Kickstart是一种用于Linux系统安装的自动化工具,它通过一个名为ks.cfg的配置文件来定义Linux安装过程中的各种参数和设置。 kickstart的工作原理 Kickstart的工作原理是通过记录典型的安装过程中所需人工干预填写的各种参数,…...
k8s-第五节-StatefulSet
StatefulSet StatefulSet 是用来管理有状态的应用,例如数据库。 前面我们部署的应用,都是不需要存储数据,不需要记住状态的,可以随意扩充副本,每个副本都是一样的,可替代的。 而像**数据库、Redis **这类…...
ai机器狗
ai机器狗的代码很早就开源了,相当于核心,最难东西美国人公开了,开源了,如果有钱,有足够资源的,造出东西有可能比公开这些核心代码的公司或者组织还好。没有技术含量,技术含量别人都解决了&#…...
数据库关键字执行顺序
在 SQL 中,关键字的执行顺序通常如下: FROM:确定要查询的表或数据源,并执行表之间的连接操作(如 INNER JOIN、LEFT JOIN 等)。FROM 子句执行顺序为从后往前、从右到左。ON:应用连接条件…...
Linux 永久挂载磁盘
文章目录 前言一、使用步骤1.命令 总结 前言 一、使用步骤 1.命令 第一步:创建挂载点 sudo mkdir /hhkj 第二步:磁盘挂载到挂载点(lsblk、lvdisplay) sudo mount /dev/sdb2 /hhkj 或者 sudo mount /dev/centos/home /hhkj 第三…...

windows启动Docker闪退Docker desktop stopped
Windows启动Docker闪退-Docker desktop stopped 电脑上很早就安装有Docker了,但是有一段时间都没有启动了,今天想启动启动不起来了,打开没几秒就闪退,记录一下解决方案。仅供参考 首先,参照其他解决方案,本…...
探索Redis GEOMETRY数据结构:地理空间索引与查询(基于Redis GEO和Java实现附近商户查找功能)
摘要 Redis是一个高性能的键值存储系统,广泛应用于缓存、消息队列、排行榜等场景。本文将介绍Redis中一个假设的GEOMETRY数据结构,用于高效地存储和查询地理空间数据。 1. Redis地理空间数据结构概述 地理空间数据结构允许用户存储地理位置信息&#…...
DP学习——策略模式
学而时习之,温故而知新。 敌人出招(使用场景) 业务中需要多个算法可替换,而不能重构代码时,怎么办?或者一个对象在运行中要根据业务切换不同的模式或者采用不同的算法,怎么办? 到…...
0701_ARM5
练习:使用usart4 main.c #include "uart4.h"int main() {// 初始化 UART4hal_uart4_init();while (1) {// 发送一个字符串//hal_put_char( hal_get_char());hal_put_string(hal_get_string());}return 0; } usart4.c #include "uart4.h"//**…...

Python用户宝典:了解并实现遗传算法
遗传算法是一种基于自然选择的技术,用于解决复杂问题。由于问题很复杂,遗传算法(而不是其他方法)被用来得出解决问题的合理方案。本文介绍遗传算法的基础知识以及如何用Python来实现。 遗传算法的要素 适应度函数 适应度函数衡…...
如何使用深度学习进行实时目标检测:速度与精度的双重挑战
如何使用深度学习进行实时目标检测:速度与精度的双重挑战 目标检测作为计算机视觉领域的核心任务之一,其目的是在图像或视频中识别和定位感兴趣的对象。随着深度学习技术的发展,基于深度学习的目标检测算法在实时性、准确性方面取得了显著进…...

创新引领,构筑产业新高地
在数字经济的浪潮中,成都树莓集团以创新驱动为核心,通过整合行业资源、优化服务、培养数字产业人才等措施,致力于打造产业高地,推动地方经济的高质量发展。 一、创新驱动,引领产业发展 1、引入新技术、新模式…...
npm,yarn清楚缓存
1.运行以下命令来清理npm缓存: npm cache clean --force或者运行以下命令清理Yarn缓存: yarn cache clean2.删除 node_modules 和锁文件: 删除 node_modules 目录和 package-lock.json 或 yarn.lock 文件,然后重新安装依赖 rm …...

大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...

【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...