【初阶数据结构】1.算法复杂度

文章目录

  • 1.数据结构前言
    • 1.1 数据结构
    • 1.2 算法
    • 1.3 如何学好数据结构和算法
  • 2.算法效率
    • 2.1 复杂度的概念
    • 2.2 复杂度的重要性
  • 3.时间复杂度
    • 3.1 大O的渐进表示法
    • 3.2 时间复杂度计算示例
      • 3.2.1 示例1
      • 3.2.2 示例2
      • 3.2.3 示例3
      • 3.2.4 示例4
      • 3.2.5 示例5
      • 3.2.6 示例6
      • 3.2.7 示例7
  • 4.空间复杂度
    • 4.1 空间复杂度计算示例
      • 4.1.1 示例1
      • 4.1.2 示例2
  • 5.常见复杂度对比
  • 6.复杂度算法题
    • 6.1 旋转数组

1.数据结构前言

1.1 数据结构

数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用，所以我们要学各式各样的数据结构。

如：线性表、树、图、哈希等

1.2 算法

算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

1.3 如何学好数据结构和算法

秘诀1：

死磕代码！！！

秘诀2：

画图画图画图+思考

2.算法效率

例题：

力扣189.轮转数组：

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

void rotate(int* nums, int numsSize, int k) {while(k--){int end = nums[numsSize-1];for(int i = numsSize - 1;i > 0 ;i--){nums[i] = nums[i-1];}nums[0] = end;}
}

这个算法是没有问题的，但是在力扣运行会报错，显示超过时间限制。

这就涉及到了复杂度这个概念。

2.1 复杂度的概念

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

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

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

2.2 复杂度的重要性

复杂度在校招中的考察已经很常见，要重点掌握。

3.时间复杂度

定义：在计算机科学中，算法的时间复杂度是一个函数式T(N)，它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运行时间呢？

  1. 因为程序运行时间和编译环境和运行机器的配置都有关系，比如同一个算法程序，用一个老编译器进行编译和新编译器编译，在同样机器下运行时间不同。

  2. 同一个算法程序，用一个老低配置机器和新高配置机器，运行时间也不同。

  3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

那么算法的时间复杂度是一个函数式T(N)到底是什么呢？这个T(N)函数式计算了程序的执行次数。

通过c语言编译链接章节学习，我们知道算法程序被编译后生成二进制指令，程序运行，就是cpu执行这 些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执行次数的函数式T(N)，假设每句指令执行时间基本一样(实际中有差别，但是微乎其微)，那么执行次数和运行时间就是等比正相关，这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。

比如解决一个问题的算法a程序T(N) = N，算法b程序T(N) = N^2，那么算法a的效率一定优于算法b。

例子：

// 请计算一下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 k = 0; k < 2 * N ; ++ k) { ++count; } int M = 10; while (M--) { ++count; } 
}

分析：

Func1 执行的基本操作次数：

T (N) = N^2^ + 2 ∗ N + 10

N = 10 T(N) = 130

N = 100 T(N) = 10210

N = 1000 T(N) = 1002010

通过对N取值分析，对结果影响最大的一项是N^2^

实际中我们计算时间复杂度时，计算的也不是程序的精确的执行次数，精确执行次数计算起来还是很麻烦的(不同的一句程序代码，编译出的指令条数都是不一样的)，计算出精确的执行次数意义也不大，因为我么计算时间复杂度只是想比较算法程序的增长量级，也就是当N不断变大时T(N)的差别。

上面我们已经看到了当N不断变大时常数和低阶项对结果的影响很小，所以我们只需要计算程序能代表增长量级的大概执行次数，复杂度的表示通常使用大O的渐进表示法。

3.1 大O的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号

推导大O阶规则

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

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

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

通过以上方法，可以得到 Func1 的时间复杂度为：O(N2 )

3.2 时间复杂度计算示例

3.2.1 示例1

// 计算Func2的时间复杂度？ 
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执行的基本操作次数：

F (N) = 2N + 10

Func2的时间复杂度为：O(N)

3.2.2 示例2

// 计算Func3的时间复杂度？ 
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执行的基本操作次数：

F (N) = M + N

因此：Func3的时间复杂度为：O(M+N)

3.2.3 示例3

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

Func4执行的基本操作次数：

F (N) = 100

根据推导规则第1条得出

Func4的时间复杂度为：O(1)

3.2.4 示例4

// 计算strchr的时间复杂度？ 
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. 若要查找的字符在字符串第一个位置，则：

    F (N) = 1

  2. 若要查找的字符在字符串最后的一个位置，则：

    F (N) = N

  3. 若要查找的字符在字符串中间位置，则：

    F (N) = N/2

因此：strchr的时间复杂度分为：

最好情况：O(1)

最坏情况：O(N)

平均情况：O(N)

总结：

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

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

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

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

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

3.2.5 示例5

// 计算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; } 
}

BubbleSort执行的基本操作次数：

  1. 若数组有序，则：

    F (N) = N

  2. 若数组有序且为降序，则：

    F (N) =[N ∗ (N + 1)] / 2

  3. 若要查找的字符在字符串中间位置，则：

因此：BubbleSort的时间复杂度取最差情况为：O(N2)

3.2.6 示例6

void func5(int n)
{int cnt = 1;while (cnt < n){cnt *= 2;}
}

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

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

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

假设执行次数为x ，则2x = n

因此执行次数：x = log n

因此：func6的时间复杂度取最差情况为：O(log2n)

注意：

log~2~n 、log n 、 lg n 的表示。

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

不同书籍的表示方式不同，以上写法差别不大，建议使用log n

3.2.7 示例7

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

调用一次Fac函数的时间复杂度为O(1)

而在Fac函数中，存在n次递归调用Fac函数

因此：

阶乘递归的时间复杂度为：O(n)

4.空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中因为算法的需要额外临时开辟的空间。

空间复杂度不是程序占用了多少bytes的空间，因为常规情况每个对象大小差异不会很大，所以空间复杂度算的是变量的个数。

空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

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

4.1 空间复杂度计算示例

4.1.1 示例1

// 计算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; } 
}

函数栈帧在编译期间已经确定好了，只需要关注函数在运行时额外申请的空间。

BubbleSort额外申请的空间有exchange等有限个局部变量，使用了常数个额外空间

因此空间复杂度为O(1)

4.1.2 示例2

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

Fac递归调用了N次，额外开辟了N个函数栈帧，每个栈帧使用了常数个空间

因此空间复杂度为：O(N)

5.常见复杂度对比

在这里插入图片描述

6.复杂度算法题

6.1 旋转数组

思路1:

时间复杂度 O(n2)

循环K次将数组所有元素向后移动K位（代码不通过）

void rotate(int* nums, int numsSize, int k) {while(k--){int end = nums[numsSize-1];for(int i = numsSize - 1;i > 0 ;i--){nums[i] = nums[i-1];}nums[0] = end;}
}

粗略估计：O(K*N) = O(n2)

思路2:

空间复杂度 O(n)

申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中

void rotate(int* nums, int numsSize, int k) 
{int newArr[numsSize];for (int i = 0; i < numsSize; ++i) {newArr[(i + k) % numsSize] = nums[i];}for (int i = 0; i < numsSize; ++i) {nums[i] = newArr[i];}
}

时间复杂度：O(n+n) = O(2n) = O(n)

空间复杂度：O(n)（因为创建了一个新数组）

思路3:

时间复杂度：O(N)

空间复杂度： O(1)

  • 前n-k个逆置：4 3 2 1 5 6 7

  • 后k个逆置 ：4 3 2 1 7 6 5

  • 整体逆置 ：5 6 7 1 2 3 4

void reverse(int* nums,int begin,int end)
{while(begin < end){//交换nums里面begin到end区域的数字int tmp = nums[begin];//交换left和right的数据nums[begin] = nums[end];nums[end] = tmp;begin++;end--;}
}void rotate(int* nums, int numsSize, int k)
{k = k%numsSize;reverse(nums,0,numsSize-k-1);//前n-k个逆置reverse(nums,numsSize-k,numsSize-1);//后k个数据逆置reverse(nums,0,numsSize-1);//整体逆置
}

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

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

相关文章

音视频开发—FFmpeg处理流数据的基本概念详解

音视频开发—FFmpeg处理流数据的基本概念详解

文章目录 多媒体文件的基本概念相关重要的结构体操作数据流的基本步骤1.解复用&#xff08;Demuxing&#xff09;2.获取流&#xff08;Stream&#xff09;3. 读取数据包&#xff08;Packet&#xff09;4. 释放资源&#xff08;Free Resources&#xff09;完整示例 多媒体文件的…
阅读更多...
基于SpringBoot构造超简易QQ邮件服务发送(分离-图解-新手)

基于SpringBoot构造超简易QQ邮件服务发送(分离-图解-新手)

目录 获取QQ 授权码 SpringBoot构建 依赖 Yaml配置 服务编写 测试 获取QQ 授权码 https://mail.qq.com/ 接着后就会有对应的密钥了 SpringBoot构建 依赖 这里的建议是 2.0系列的Springboot版本用低一点的邮件依赖 <!-- 电子邮件 --> <dependency>&…
阅读更多...
字节码编程javassist之生成带有注解的类

字节码编程javassist之生成带有注解的类

写在前面 本文看下如何使用javassist生成带有注解的类。 1&#xff1a;程序 测试类 package com.dahuyou.javassist.huohuo.cc;import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import ja…
阅读更多...
神经网络设计过程

神经网络设计过程

1.可根据Iris特征直接判断 2.神经网络方法&#xff0c;采集大量的Iris特征&#xff0c;分类对应标签&#xff0c;构成数据集。 将数据集喂入搭好的神经网络结构&#xff0c;网络通过反向传播优化参数得到模型。 有新的网络送入到模型里&#xff0c;模型会给出识别结果。 3.…
阅读更多...
低空经济火爆：无人机培训机构工作开展详解

低空经济火爆：无人机培训机构工作开展详解

随着低空经济的迅速崛起&#xff0c;无人机技术在多个领域得到了广泛应用&#xff0c;从航拍摄影、农业植保到物流配送、环境监测等&#xff0c;都显示出了巨大的市场潜力。无人机培训机构作为培养专业无人机驾驶和操作人才的摇篮&#xff0c;在低空经济的发展中扮演着至关重要…
阅读更多...
Vue项目openlayers中使用jsts处理wkt和geojson的交集-(geojson来源zpi解析)

Vue项目openlayers中使用jsts处理wkt和geojson的交集-(geojson来源zpi解析)

Vue项目openlayers中使用jsts处理wkt和geojson的交集-(geojson来源zpi解析) 读取压缩包中的shape看上一篇笔记&#xff1a;Vue项目读取zip中的ShapeFile文件&#xff0c;并解析为GeoJson openlayers使用jsts官方示例&#xff1a;https://openlayers.org/en/latest/examples/j…
阅读更多...
已解决 javax.xml.transform.TransformerFactoryConfigurationError 异常的正确解决方法，亲测有效！！！

已解决 javax.xml.transform.TransformerFactoryConfigurationError 异常的正确解决方法，亲测有效！！！

已解决 javax.xml.transform.TransformerFactoryConfigurationError 异常的正确解决方法&#xff0c;亲测有效&#xff01;&#xff01;&#xff01; 目录 一、问题分析 二、报错原因 三、解决思路 四、解决方法 五、总结 博主v&#xff1a;XiaoMing_Java 博主v&#x…
阅读更多...
昇思25天学习打卡营第16天|Vision Transformer图像分类

昇思25天学习打卡营第16天|Vision Transformer图像分类

昇思25天学习打卡营第16天|Vision Transformer图像分类 前言Vision Transformer图像分类Vision Transformer&#xff08;ViT&#xff09;简介模型结构模型特点 环境准备与数据读取模型解析Transformer基本原理Attention模块 Transformer EncoderViT模型的输入整体构建ViT 模型训…
阅读更多...
【自学网络安全】：安全策略与用户认证综合实验

【自学网络安全】：安全策略与用户认证综合实验

实验拓扑图&#xff1a; 实验任务&#xff1a; 1、DMZ区内的服务器&#xff0c;办公区仅能在办公时间内(9:00-18:00)可以访问&#xff0c;生产区的设备全天可以访问 2、生产区不允许访问互联网&#xff0c;办公区和游客区允许访问互联网 3、办公区设备10.0.2.10不允许访问Dmz区…
阅读更多...
代理详解之静态代理、动态代理、SpringAOP实现

代理详解之静态代理、动态代理、SpringAOP实现

1、代理介绍 代理是指一个对象A通过持有另一个对象B&#xff0c;可以具有B同样的行为的模式。为了对外开放协议&#xff0c;B往往实现了一个接口&#xff0c;A也会去实现接口。但是B是“真正”实现类&#xff0c;A则比较“虚”&#xff0c;他借用了B的方法去实现接口的方法。A…
阅读更多...
未羽研发测试管理平台

未羽研发测试管理平台

突然有一些觉悟&#xff0c;程序猿不能只会吭哧吭哧的低头做事&#xff0c;应该学会怎么去展示自己&#xff0c;怎么去宣传自己&#xff0c;怎么把自己想做的事表述清楚。 于是&#xff0c;这两天一直在整理自己的作品&#xff0c;也为接下来的找工作多做点准备。接下来…
阅读更多...
wordpress外贸建站公司案例英文模板

wordpress外贸建站公司案例英文模板

Indirect Trade WP外贸网站模板 WordPress Indirect Trade外贸网站模板&#xff0c;建外贸独立站用wordpress模板&#xff0c;快速搭建十分便捷。 衣物清洁wordpress独立站模板 洗衣粉、洗衣液、衣物柔顺剂、干洗剂、衣领净、洗衣皂等衣物清洁wordpress独立站模板。 家具wordpr…
阅读更多...
Apache部署与配置

Apache部署与配置

概述 介绍 Apache HTTP Server(简称Apache)是Apache的一个开源的网页服务器&#xff0c;它源自NCSAhttpd服务器&#xff0c;并经过多次修改和发展&#xff0c;如今已经成为全球范围内广泛使用的Web服务器软件之一 特点 跨平台&#xff1a;可以运行在几乎所有广泛使用的计算机平…
阅读更多...
哪个充电宝口碑比较好？怎么选充电宝？2024年口碑优秀充电宝推荐

哪个充电宝口碑比较好？怎么选充电宝？2024年口碑优秀充电宝推荐

在如今快节奏的生活中&#xff0c;充电宝已然成为我们日常生活中的必备品。然而&#xff0c;市场上充电宝品牌众多&#xff0c;质量参差不齐&#xff0c;如何选择一款安全、可靠且口碑优秀的充电宝成为了消费者关注的焦点。安全性能不仅关系到充电宝的使用寿命&#xff0c;更关…
阅读更多...
【正点原子i.MX93开发板试用连载体验】项目计划和开箱体验

【正点原子i.MX93开发板试用连载体验】项目计划和开箱体验

本文最早发表于电子发烧友&#xff1a;【　　　】【正点原子i.MX93开发板试用连载体验】基于深度学习的语音本地控制 - 正点原子学习小组 - 电子技术论坛 - 广受欢迎的专业电子论坛! (elecfans.com)https://bbs.elecfans.com/jishu_2438354_1_1.html 有一段时间没有参加电子发…
阅读更多...
clickhouse-jdbc-bridge rce

clickhouse-jdbc-bridge rce

clickhouse-jdbc-bridge 是什么 JDBC bridge for ClickHouse. It acts as a stateless proxy passing queries from ClickHouse to external datasources. With this extension, you can run distributed query on ClickHouse across multiple datasources in real time, whic…
阅读更多...
支持向量机 （support vector machine，SVM）

支持向量机 （support vector machine，SVM）

支持向量机 &#xff08;support vector machine&#xff0c;SVM&#xff09; flyfish 支持向量机是一种用于分类和回归的机器学习模型。在分类任务中&#xff0c;SVM试图找到一个最佳的分隔超平面&#xff0c;使得不同类别的数据点在空间中被尽可能宽的间隔分开。 超平面方…
阅读更多...
MMGPL: 多模态医学数据分析与图提示学习| 文献速递-基于深度学习的多模态数据分析与生存分析

MMGPL: 多模态医学数据分析与图提示学习| 文献速递-基于深度学习的多模态数据分析与生存分析

Title 题目 MMGPL: Multimodal Medical Data Analysis with Graph Prompt Learning MMGPL: 多模态医学数据分析与图提示学习 01 文献速递介绍 神经学障碍&#xff0c;包括自闭症谱系障碍&#xff08;ASD&#xff09;&#xff08;Lord等&#xff0c;2018年&#xff09;和阿…
阅读更多...
kafka的副本replica

kafka的副本replica

指定topic的分区和副本 通过kafka命令行工具 kafka-topics.sh --create --topic myTopic --partitions 3 --replication-factor 1 --bootstrap-server localhost:9092 执行代码时指定分区个数
阅读更多...
基于Spring Boot框架的EAM系统设计与实现

基于Spring Boot框架的EAM系统设计与实现

摘 要&#xff1a;文章设计并实现一个基于Spring Boot框架的EAM系统&#xff0c;以应对传统人工管理模式存在的低效与信息管理难题。系统利用Java语言、JSP技术、MySQL数据库等技术栈&#xff0c;构建了一个B/S架构的高效管理平台&#xff0c;提升了资产管理的信息化水平。该系…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发