24/07/02数据结构(1.1201)算法效率顺序表

数据结构基本内容:1.时间复杂度 空间复杂度2.顺序表链表3.栈 队列4.二叉树5.排序

数据结构是存储,组织数据的方式.指相互之间存在一种或多种特定关系的数据元素的集合

算法是定义良好的计算过程.取一个或一组值为输入并产生一个或一组值为输出.

需要知道虽然选择题有20-30个代码题3-4个但是来开分差的都是代码题.

先理解再多加练习,数据结构差不多了去看看剑指学学思路.刷完这些内容之后坚持刷刷leetcode.

算法效率分为两种:一种是时间效率一种是空间效率.现在不怎么需要担心空间性,主要需要注意时间效率.

时间复杂度

时间复杂度:算法中基本操作的执行次数称为算法的事件复杂度.并不关系具体一个指令多少秒.

在这里 ++count 就是基本操作;两层循环嵌套,外层执行N次,内层也执行N次,所以基本操作有N ^ 2

所以认为它的时间复杂度是N ^ 2;

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

N = 10 F(N) = 130

N = 100 F(N) = 10210

N = 1000 F(N) = 1002010

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

大O符号:适用于描述函数渐进行为的数学符号.

推导大O阶方法:

1.用常数1取代运行时间中的所有加法常数.

2.在修改后的运行次数函数中,只保留最高阶项

3.如果最高阶项存在且不是1,则去除与这个项目相乘的常数.得到的就是大O阶.

使用大O阶渐进表示法后,Func1的时间复杂度为:

        O(N^2)

计算冒泡排序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 - 1,n - 2,n - 3...0

最坏:F(n):n(n+1)/2 = 1/2 * n ^ 2 +1/2 * n

所以时间复杂度O(n ^ 2)

二分查找的时间复杂度O(lgn)

//计算阶乘递归Factorial时间复杂度

<表达式1>?<表达式2>:<表达式3> 在运算中,首第一个表达式进行检验,如果为真,则返回表达式2的值;如果为假,则返回表达式3的值。
long long Factorial(size_t N){
    return N < 2 ? N : Factorial(N - 1) * N;
}

F(N)-->F(N-1)-->F(N-2)-->...-->1.需要N个递归调用,所以它的时间复杂度O(N).

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

F(N)

F(N-1)F(N-2)

F(N-2)F(N-3)F(N-3)F(N-4)

......

F(1)

时间复杂度时O(2 ^ N).

空间复杂度

空间复杂度是一个算法在运行过程中临时占用存储空间大小的度量.空间复杂度不是程序占用了多少字节的空间,它计算的是变量的个数,基本和时间复杂度类似,也是用大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;
    }
}

变量的个数5个是常数个所以空间复杂度是O(1).

//计算斐波那契递归Fibonacci的空间复杂度
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 + 常数.所以空间复杂度是O(n).

//计算阶乘递归Factorial空间复杂度
long long Factorial(size_t N){
    return N < 2 ? N : Factorial(N - 1) * N;
}

因为局部变量都是放在函数栈里,每调用一次函数会有一个函数栈,里面有一个变量N所以空间复杂度是O(n).

顺序表和链表

1.线性表2.顺序表3.链表4.顺序表和链表的区别和联系

线性表是n个具有相同特征的数据元素的有限序列.常见的线性表:顺序表 链表 栈 队列 数组...

线性表在逻辑上是线性的,也就是连续的一条直线,但它在物理结构上不一定是连续的,如果物理结构上连续是顺序表,如果物理上不连续就是链表.

顺序表是一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.在数组上完成数据的增删改查.

1.静态顺序表:使用定长数组存储

2.动态顺序表:使用动态开辟的数组存储

//顺序表的静态存储
#define N 10
typedef int SLDataType;

typedef struct SeqList{
    SLDataType array[N]; //定长数组
    size_t size;         //有效数据的个数
}SeqList;
 

//顺序表的动态存储
typedef int SLDataType;
typedef struct seqList{
    SLDataType*_data;//需要动态开辟的数组
    size_t _size;//有效元素的个数
    size_t _capacity;//当前可以存放的最大元素个数
}seqList;

静态数据表是开在栈上的,如果开太大会导致栈溢出

而动态数据表的大小只是一个指针加两个整数.

sizeof(静态):包含数组大小;sizeof(动态):不包含数组大小

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

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

相关文章

MyBatis-plus这么好用,不允许还有人不会

你好呀&#xff0c;我是 javapub. 做 Java 的同学都会用到的三件套&#xff0c;Spring、SpringMV、MyBatis。但是由于使用起来配置较多&#xff0c;依赖冲突频发。所有&#xff0c;各路大佬又在这上边做了包装&#xff0c;像我们常用的 SpringBoot、MyBatisPlus。 基于当前要…

[Python学习篇] Python函数

定义函数 语法&#xff1a;使用关键字 def def 函数名(参数): 代码1 代码2 ...... 调用函数 语法&#xff1a; 函数名(参数) 注意&#xff1a;不同的需求&#xff0c;参数可有可无。在Python中&#xff0c;函数必须先定义后使用 示例&#xff1a; # 定义函数 d…

WPDRRC信息安全体系架构模型

构建信息安全保障体系框架应包括技术体系、组织机构体系和管理体系等三部分&#xff0c;也就是说&#xff1a;人、管理和技术手段是信息安全架构设计的三大要素&#xff0c;而构成动态的信息与网络安全保障体系框架是实现系统的安全保障。 1.WPDRRC信息安全模型的定义 WPDRRC…

书城在线系统:基于Java和SSM框架的高效信息管理平台

开头语&#xff1a;你好呀&#xff0c;我是计算机学长猫哥&#xff01;如果有相关需求&#xff0c;文末可以找到我的联系方式。 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SSM框架&#xff08;Spring, Spring MVC, Mybatis&#xff09; 工具&…

【面试系列】AI研究员高频面试题及详细解答

欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;欢迎订阅相关专栏&#xff1a; ⭐️ 全网最全IT互联网公司面试宝典&#xff1a;收集整理全网各大IT互联网公司技术、项目、HR面试真题. ⭐️ AIGC时代的创新与未来&#xff1a;详细讲解AIGC的概念、核心技术、…

图形对象句柄及属性对象句柄

句柄 句柄引用图形对象的具体实例。使用对象句柄设置和查询对象属性的值。 对象的句柄值,类似于编程时的引用,将对象的句柄值赋值给变量后,该变量就可以代表指定的绘图对象。 当创建图形对象时&#xff0c;可以将对象的句柄保存到变量中。 x 1:10; y x.^2; h plot(x,y); …

【开发环境】MacBook M系列芯片环境下搭建完整Python开发环境

文章目录 Anaconda和Python的关系&#xff1f;1. Python2. Anaconda 安装AnacondaPycharm整合Anaconda运行你的Python代码 Anaconda和Python的关系&#xff1f; 如果有简单了解过Python语言的&#xff0c;那么你很容易就会听到有人会叫你安装Anaconda。 那么Anaconda是什么&am…

如何寻找一个领域的顶级会议,并且判断这个会议的影响力?

如何寻找一个领域的顶级会议&#xff0c;并且判断这个会议的影响力&#xff1f; 会议之眼 快讯 很多同学都在问&#xff1a;学术会议不是期刊&#xff0c;即使被SCI检索&#xff0c;也无法查询影响因子。那么如何知道各个领域的顶级会议&#xff0c;并对各个会议有初步了解呢…

用AI,每天创作200+优质内容,2分钟教会你操作!

前段时间发布了这篇“寻找爆款文案及标题的9大渠道&#xff0c;直接搬运都能搞流量&#xff01;”&#xff0c;里面我讲到如何寻找爆款标题。最近不少朋友问我&#xff0c;如何创作这个标题相关的内容。 多数平台都有风控规则&#xff0c;有些平台内容也会有字数要求。为了让大…

动态规划算法,完全零基础小白教程!不是计算机的都能学会!万字吐血详解。

目录 一、动态规划算法概念 题一 1、算法解析 1&#xff09;确定状态&#xff1a; ​2&#xff09;状态转移方程&#xff1a; ​3&#xff09;初始化&#xff1a; 4&#xff09;填表顺序&#xff1a; 5&#xff09;返回值&#xff1a; 2、代码 题二 1、算法解析 1、确…

2Python的Pandas:读取数据

1.读取Excel文件 1.1.读取数据 import pandas as pd# Excel 文件的 URL 或本地路径 url "https://www.gairuo.com/file/data/dataset/team.xlsx"# 使用 Pandas 的 read_excel 函数读取数据 try:df pd.read_excel(url)print(df.head()) # 打印 DataFrame 的前几行…

【Node-RED 4.0.2】4.0版本新增特性(官方版)

二、重要功能 *1.时间戳格式改进 过去&#xff0c;node-red 只提供了 最原始的 timestamp 的格式&#xff08;1970-01-01 ~ now&#xff09; 但是现在&#xff0c;额外增加了 2 种格式&#xff1a; ISO 8601 -A COMMON FORMAT&#xff08;YYYY-MM-DDTHH:mm:ss:sssZ&#xff…

《昇思25天学习打卡营第9天|onereal》

继续学习昨天的 基于MindNLPMusicGen生成自己的个性化音乐 生成音乐 MusicGen支持两种生成模式&#xff1a;贪心&#xff08;greedy&#xff09;和采样&#xff08;sampling&#xff09;。在实际执行过程中&#xff0c;采样模式得到的结果要显著优于贪心模式。因此我们默认启…

电巢直播中国星坤:让每次连接都有改变世界的能力

连接器作为电子设备中不可或缺的关键组件&#xff0c;发挥着至关重要的作用。连接器是电子电路中的“桥梁”&#xff0c;在器件与组件、组件与机柜、系统与子系统之间起电连接和信号传递的作用。连接器的好坏会直接影响整个系统的可靠性和运行效率&#xff0c;一旦出现问题&…

【问题已解决】Vue管理后台,点击登录按钮,会发起两次网络请求(竟然是vscode Compile Hero编译插件导致的)

问题 VueElement UI 做的管理后台&#xff0c;点击登录按钮&#xff0c;发现 接口会连续掉两次&#xff0c;发起两次网络请求&#xff0c;但其他接口都是正常调用的&#xff0c;没有这个问题&#xff0c;并且登录按钮也加了loading&#xff0c;防止重复点击&#xff0c;于是开…

Dify自定义工具例子

1.天气&#xff08;JSON&#xff09; {"openapi": "3.1.0","info": {"title": "Get weather data","description": "Retrieves current weather data for a location.","version": "v1…

linux和mysql基础指令

Linux中nano和vim读可以打开记事文件。 ifdown ens33 ifup ens33 关闭&#xff0c;开启网络 rm -r lesson1 gcc -o code1 code1.c 编译c语言代码 ./code1 执行c语言代码 rm -r dir 删除文件夹 mysql> show databases-> ^C mysql> show databases; -------…

鸿蒙开发设备管理:【@ohos.multimodalInput.touchEvent (触摸输入事件)】

触摸输入事件 设备上报的触屏事件。 说明&#xff1a; 本模块首批接口从API version 9开始支持。后续版本的新增接口&#xff0c;采用上角标单独标记接口的起始版本。 导入模块 import {Action,ToolType,SourceType,Touch,TouchEvent} from ohos.multimodalInput.touchEvent;…

Android高级面试_8_热修补插件化等

Android 高级面试&#xff1a;插件化和热修复相关 1、dex 和 class 文件结构 class 是 JVM 可以执行的文件类型&#xff0c;由 javac 编译生成&#xff1b;dex 是 DVM 执行的文件类型&#xff0c;由 dx 编译生成。 class 文件结构的特点&#xff1a; 是一种 8 位二进制字节…

Linux指定文件权限的两种方式-符号与八进制数方式示例

一、指定文件权限可用的两种方式&#xff1a; 对于八进制数指定的方式&#xff0c;文件权限字符代表的有效位设为‘1’&#xff0c;即“rw-”、“rw-”、“r--”&#xff0c;以二进制表示为“110”、“110”、“100”&#xff0c;再转换为八进制6、6、4&#xff0c;所以777代表…