空间复杂度 线性表，顺序表尾插。

2024-06-22 16:04
文章标签 复杂度 空间 顺序 线性表 表尾

本文主要是介绍空间复杂度 线性表，顺序表尾插。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

各位少年，大家好，我是那一脸阳光，本次分享的主题是时间复杂度和空间复杂度 还有顺序表文章讲解和分享，如有不对可以评论区指导。
在这里插入图片描述

时间复杂度例题

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

这块的时间复杂度为O（2^N)次方 可以看到这个代码是个等比数列，我们通过下面的图举个例子。
0
在这里插入图片描述
我们发现每次FIb（N）开始每次递归都变成两个，然后通过错位即可算出 FN的公式是2^(n-1)-1,这个减一是减刚开始项。
OJ题消失的数字
https://leetcode-cn.com/problems/missing-number-lcci/
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

{int x = 0;for (int i = 0; i < numsSize; i++){x ^= nums[i];}for (int i = 0; i < numsSize+1; i++){x ^= i;}return x;
}

这段代码是一段单身狗问题，1^1是0 ，22也是0大家注意第二个循环即可，这种题一般非常的简单的，0a都是0 如果对这里不太懂 可以复习一下单身狗问题。

空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因
此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
在这里插入图片描述

冒泡排序的空间复杂度


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

冒泡排序的时间复杂度在O（N^2),空间复杂度是O（1），因为这个没有额外消耗，或者有代码创造变量。

 // 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
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

这段代码时间复杂度是O（N），空间复杂度也是O（N），因为这里的动态内存分配开辟了n+1个空间。

递归的空间复杂度

例子一
// 计算阶乘递归Fac的空间复杂度？

long long Fac(size_t N){if(N == 0)return 1;return Fac(N-1)*N;}

这里的每次递归都在栈中创建空间，每次递归都会创建一定的空间，所以空间复杂度是O（N）。

常见复杂度对比
一般算法常见的复杂度如下：
在这里插入图片描述
在这里插入图片描述
OJ题 逆置
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
在这里插入图片描述
这里比如说N是7 K是3 前三段逆置，后四个再逆置，最后整体逆置，但是这种方法一般人能不出来，所以还有其他方法，这段代码时间复杂度是O（N^2)，空间复杂度是O（1），这里接受另外一种写法 比较常用的 空间换时间。

在这里插入图片描述
这里我们开创一个a的时间 再开创一个tmp数组，然后再把tmp数组拷贝到a数组里头，然后销毁tmp数组即可，这样以空间换时间的方法。

这道题中三段逆置最优，其次就是空间换时间，这种方法是最优的，但空间复杂度会上涨到O（N）

 void reverse(int*a,int left,int right){while(left<right){int tmp=a[left];a[left]=a[right];a[right]=tmp;++left--right;}}void rotate(int*nums,int numsSize,int k)if（k>numsSize)k%=numsSize;reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-1);}

这段代码，完成了 三段三次逆置，接下来介绍空间换时间的逆置方法。
void rotate(int*nums,int numsSize,int k)
{
if(k>numsSize)
k%=numsSize； 
int*tmp=(int*)malloc(sizeof(int)*numsSize);
memcpy(tmp+k,nums,sizeof(int)*(numsSize-k);
memcpy(tmp,nums+numsSize-k,sizeof(int）*（k)）；
memcpy(nums,tmp.sizeof(int)*(numsSize));
free(tmp);
tmp=NULL;
}

线性表

线性表（linear list）
是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结
构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
在这里插入图片描述

u在这里插入图片描述
顺序表本质是数组，如果我们想在顺序表删除第一个人 我们删除的方法就是覆盖。
在这里插入图片描述
每个数据都往前进去一步，这样就可以实现删除覆盖了。
在这里插入图片描述
上面是静态顺序表 数组长度 和有效数据个数。
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪
费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表 我们实现一下 尾插

#include"SeqList.h"
void SLInit(SL* psl)
{psl->a = (SLDatatype*)malloc(sizeof(SLDatatype)*4);if (psl->a == NULL){perror("malloc fail");return;}psl->capacity = 4;psl->size = 0;
}void SLDestroy(SL* psl)
{free(psl->a);psl->a = NULL;psl->size = 0;psl->capacity = 0;
}void SLPrint(SL* psl)
{for (int i = 0; i < psl->size; i++){printf("%d ", psl->a[i]);}printf("\n");
}void SLCheckCapacity(SL* psl)
{if (psl->size == psl->capacity){SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}psl->a = tmp;psl->capacity *= 2;}
}void SLPushBack(SL* psl, SLDatatype x)
{//psl->a[psl->size] = x;//psl->size++;SLCheckCapacity(psl);psl->a[psl->size++] = x;
}void SLPushFront(SL* psl, SLDatatype x);
void SLPopBack(SL* psl);
void SLPopFront(SL* psl);

这里主要实现三个部分 创建空间 释放空间，然后通过数组进行尾部插入，这里只实现了最简单的尾插。剩下部分 我给大家写出来 大家可以去编译器敲一敲。2

#pragma once
#include<stdio.h>
#include<stdlib.h>// 静态的顺序表
// 给小了不够用，给多了浪费
//#define N 10000
//typedef int SLDatatype;
//struct SeqList
//{
//	SLDatatype a[N];
//	int size;
//};// 动态顺序表
//typedef double SLDatatype;
typedef int SLDatatype;
typedef struct SeqList
{SLDatatype* a;int size;       // 存储的有效数据的个数int capacity;   // 容量
}SL;void SLInit(SL* psl);
void SLDestroy(SL* psl);void SLPrint(SL* psl);//STL命名风格
void SLPushBack(SL* psl, SLDatatype x);
void SLPushFront(SL* psl, SLDatatype x);
void SLPopBack(SL* psl);
void SLPopFront(SL* psl);

#include "SeqList.h"int main()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPushBack(&s, 6);SLPushBack(&s, 6);SLPushBack(&s, 6);SLPushBack(&s, 6);SLPrint(&s);SLDestroy(&s);return 0;
}

这篇关于空间复杂度 线性表，顺序表尾插。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1084752。

相关文章

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,：本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一：“杨辉三角”题目链接二：题解代码：三：题解思路：总结一：“杨辉三角”题目链接题目链接：点击这里
阅读更多...
顺序表之创建，判满，插入，输出

顺序表之创建，判满，插入，输出

文章目录 🍊自我介绍🍊创建一个空的顺序表，为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了，满了返回值1，否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾”
阅读更多...
web群集--nginx配置文件location匹配符的优先级顺序详解及验证

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配（Exact Match）2. 正则表达式匹配（Regex Match）3. 前缀匹配（Prefix Match） 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中，location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求，NGINX 提供了多种匹
阅读更多...
LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵，找出只包含 1 的最大正方形，并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划
阅读更多...
【高等代数笔记】线性空间（一到四）

【高等代数笔记】线性空间（一到四）

3. 线性空间 令 K n : = { ( a 1 , a 2 , . . . , a n ) ∣ a i ∈ K , i = 1 , 2 , . . . , n } \textbf{K}^{n}:=\{(a_{1},a_{2},...,a_{n})|a_{i}\in\textbf{K},i=1,2,...,n\} Kn:={(a1​,a2​,...,an​)∣ai​∈K,i=1,2,...,n
阅读更多...
算法复杂度的简单介绍

算法复杂度的简单介绍

算法复杂度是衡量算法执行效率和资源消耗的指标，通常分为时间复杂度和空间复杂度。时间复杂度评估算法执行所需时间随输入规模的变化，空间复杂度评估算法占用内存的增长情况。复杂度通常用大O符号来表示，它描述了最坏情况下的增长速率。 1. 时间复杂度 时间复杂度表示算法执行所需时间随输入规模 nnn 的变化关系。常见的时间复杂度如下（从快到慢）： a. 常数时间：O(1) 不管输入大小如何，算法总是
阅读更多...
LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

3177. 求出最长好子序列 II 题目链接 题目描述 给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标i满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。 实例1: 输入：nums = [1,2,1,1,3],
阅读更多...
win7系统中C盘空间缩水的有效处理方法

win7系统中C盘空间缩水的有效处理方法

一、深度剖析和完美解决 　　1、 休眠文件 hiberfil.sys : 　　该文件在C盘根目录为隐藏的系统文件，隐藏的这个hiberfil.sys文件大小正好和自己的物理内存是一致的，当你让电脑进入休眠状态时，Windows 7在关闭系统前将所有的内存内容写入Hiberfil.sys文件。 　　而后，当你重新打开电脑，操作系统使用Hiberfil.sys把所有信息放回内存，电脑
阅读更多...
求空间直线与平面的交点

求空间直线与平面的交点

若直线不与平面平行，将存在交点。如下图所示，已知直线L过点m（m1，m2，m3），且方向向量为VL（v1，v2，v3），平面P过点n（n1，n2，n3），且法线方向向量为VP（vp1，vp2，vp3），求得直线与平面的交点O的坐标（x，y，z）： 将直线方程写成参数方程形式，即有： x = m1+ v1 * t y = m2+ v2 * t
阅读更多...
数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2