算法的复杂度

news/2024/12/3 1:37:46/

1.数据结构前言

下面的概念有的比较难理解,做个了结就行。

1.1数据结构的起源

在现实生活中我们更多地并不是解决数值计算的问题,而是 需要一些更科学的手段如(表,数,图等数据结构),才能更好地处理问题。所以数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及他们之间的关系和操作等相关问题的学科。

1968年,美国高德纳教授在其所写的《计算机程序设计艺术》第一卷《基本算法》中,较系统的阐述了数据的逻辑结构及其操作。

1.2数据结构Data Structure)的定义

数据结构:相互之间存在一种或者多种关系的数据元素的集合

数据元素:是组成数据的,有一定意义的基本单位,在计算机中被当做成体处理。也叫做记录。比如在人类社会中,它的数据元素就是人。畜类中,牛羊猪等就是它的数据元素。

数据项:一个数据元素可以由多个数据项组成。比如人的数据项可以由眼睛、鼻子、嘴巴等等。

数据对象:具有相同性质的数据元素的集合,是数据的子集。比如人都有生日、姓名、性别,把这些拥有相同数据项的数据元素就称为相同性质的数据元素。

1.3逻辑结构与物理结构

1.3.1逻辑结构

逻辑结构:数据元素之间的相互关系。

常见的逻辑结构:

集合结构:(”平等“)

线性结构:(一对一)

树形结构:(一对多)

图形结构:(多对多)

1.3.2物理结构

物理结构:指的是数据的逻辑结构在计算机中的存储方式

存储结构的分类:顺序存储结构、链式存储结构

顺序存储结构:把数据元素存放在连续的内存空间中,这种的结构的物理结构与逻辑结构是相同的

链式存储结构:把数据元素存放在任意的内存空间中,这个任意可以连续也可以不连续。

这种存储结构的操作是建立在指针域上的,因为你总得通过一个手段去找到这些元素。

1.4抽象数据类型

1.4.1数据类型

数据类型:只一组具有相同性质的的集合以及定义在此集合上面的一组操作的总称。

高级语言中,类型往往指代的是变量、常量、表达式所能表示的范围,还有所能进行的+ - * /等一系列操作。

在C语言中,数据类型分为:

原子类型:不可再分的基本单位,包括整形、浮点型、字符型

结构类型:由若干个类型组合而成,可以再分。比如:一个整形数组就包含若干个整形数据。

1.4.2抽象数据类型

抽象是指抽出事物具有的本质属性

抽象数据类型:是指一个数学模型以及定义在该模型上面的一组操作。

对于抽象数据类型,我们并不关注数据本身的物理结构,而是关注它的数学抽象特征。

一个抽象数据类型定义了:一个数据对象、数据元素中各数据元素之间的关系及对数据的操作。

2.算法的复杂度

在次之前我们先看一个例题:189. 轮转数组 - 力扣(LeetCode)

经过考虑我们可以有三种解法:

1.挨个轮转

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

2.取余挨个轮转:

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

3.面向结果编程:

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

4.三次逆序法:

void Reverse(int* nums,int low,int high){while(low<high){int tmp=nums[low];nums[low]=nums[high];nums[high]=tmp;low++;high--;}
}
void rotate(int* nums, int numsSize, int k) {k%=numsSize;Reverse(nums,0,numsSize-k-1);Reverse(nums,numsSize-k,numsSize-1);Reverse(nums,0,numsSize-1);}

2.1时间复杂度

先说明一下:上述方法的1、2的关系为优化。3、4是使用了不同的算法。

2.1.1时间复杂度的定义

时间复杂度:在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)数量级。算法的时间复杂度,也就是算法的时间量度,记作T(n)=O(f(n))。它表示随着问题规模n的增大,算法的执行时间的增长率和符f(n)的增长率相同,称作算法的渐进时间复杂度,简称时间复杂度。其中符f(n)是问题规模n的某个函数。

这里我们从定义中提取几个关键点:

1.算法时间复杂度是算法渐进时间复杂度的简称。

2.它表示的是一种变化趋势(随问题规模)或者增长率。

3.并不是一个确切的语句到底执行多少次的函数表达式。

2.1.2算法时间复杂度的大O渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为的数学符号
💡 推导⼤O阶规则
1. 时间复杂度函数式 T(N) 中,只保留最⾼阶项,去掉那些低阶项,因为当 N 不断变大时,
低阶项对结果影响越来越小,当 N 无穷大时,就可以忽略不计了。
2. 如果最高阶项存在且不是 1 ,则去除这个项目的常数系数,因为当 N 不断变大,这个系数
对结果影响越来越小,当 N 无穷大时,就可以忽略不计了。
3. T(N) 中如果没有 N 相关的项目,只有常数项,用常数 1 取代所有加法常数。

2.1.3算法时间复杂度的例题:

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

T(n)=2*n+10(只关注循环的额外开销)

时间复杂度:O(n)

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

同样的时间复杂度:O(n)

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

O(1)

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

这是一个查找某个字符的算法,但是不同情况有不同的复杂度有不同划分:

假设要找的就在第一个字符位置(或常数个):T(n)=k(常数) --> O(1)4

假设要找的在最后一个位置:T(n)=n --> O (n)

假设要找的在中间:T(n)=n/2 --> O(n)

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

T(n)=N*(N+1)/2 -->O(n)=n^2

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

O(n)=logn  这里写成lnn lgn都行,因为我们说时间复杂度表示的是变化率,所以只需要表示出来对数阶就可以。

2.1.3.7

递归的时间复杂度

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

O(n)=n

递归时间复杂度的求法=单次递归的时间复杂度*递归次数

2.1.4常见的时间复杂度

2.2.空间复杂度

空间复杂度也是⼀个数学表达式,是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占⽤了多少bytes的空间,因为常规情况每个对象大小差异不会很大,所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进表示法
注意:函数运行时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定
当不加限定的说复杂度时一般指代的是时间复杂度,所以空间复杂度的讨论并不会很深入。
例题:
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(1)

3.轮转数组复杂度分析

法一:O(n^2)    O(1)

法二:O(n^2)    O(1)

法三:O(n)       O(n)

法四:O(n)       O(1)


http://www.ppmy.cn/news/1551894.html

相关文章

分类预测 | Matlab实现GA-XGBoost分类预测

分类预测 | Matlab实现GA-XGBoost分类预测 目录 分类预测 | Matlab实现GA-XGBoost分类预测分类效果基本描述程序设计参考资料分类效果 基本描述 1.Matlab实现GA-XGBoost分类预测 2.输入多个特征,输出多类,可视化展示分类准确率。 3…程序语言为matlab,程序可出分类效果图,混…

Flink四大基石之CheckPoint

1、State Vs Checkpoint State:状态,是Flink中某一个Operator在某一个时刻的状态,如maxBy/sum,注意State存的是历史数据/状态,存在内存中。 Checkpoint:快照点, 是Flink中所有有状态的Operator在某一个时刻的State快照信息/存档信息。 一句话概括: Checkpoint就是State的快照…

若依项目源码阅读

源码阅读 前端代码分析 代码生成器生成的前端代码有两个&#xff0c;分别是course.js用于向后端发送ajax请求的接口代码&#xff0c;另一个是index.vue&#xff0c;用于在浏览器展示课程管理的视图组件。前端的代码是基于vue3elementplus。 template用于展示前端组件别的标签…

『VUE』elementUI dialog的子组件created生命周期不刷新(详细图文注释)

目录 1. 测试代码分析令人迷惑的效果 分析原因解决方法 如何在dialog中反复触发created呢?总结 欢迎关注 『VUE』 专栏&#xff0c;持续更新中 欢迎关注 『VUE』 专栏&#xff0c;持续更新中 主要是在做表单的时候想要有一个编辑表单在dialog弹窗中出现,同时dialog调用的封装的…

【Linux】-操作系统

&#x1f511;&#x1f511;博客主页&#xff1a;阿客不是客 &#x1f353;&#x1f353;系列专栏&#xff1a;深入代码世界&#xff0c;了解掌握 Linux 欢迎来到泊舟小课堂 &#x1f618;博客制作不易欢迎各位&#x1f44d;点赞⭐收藏➕关注 ​​ 一、冯•诺依曼架构&#xff…

挑战用React封装100个组件【003】

项目地址 https://github.com/hismeyy/react-component-100 组件描述 组件适用于展示个人信息 样式展示 前置依赖 今天我们的这个挑战需要用用到了 react-icons 依赖&#xff0c;因此&#xff0c;我们需要先安装它。 # 使用 npm npm install react-icons# 或者使用 yarn …

组播基础实验

当需要同时发给多个接受者或者接收者ip未知时使用组播 一、组播IP地址 1、组播IP地址范围 组播地址属于D类地址&#xff1a;224.0.0.0/4&#xff08;224.0.0.0-239.255.255.255&#xff09; 2、分类 &#xff08;1&#xff09;链路本地地址&#xff08;link-local&#xf…

使用 Docker 容器创建一个 Web 服务器:从入门到实践

目录 Docker 与容器技术简介准备工作通过 Docker 创建一个简单的 Web 服务器 基于官方 Nginx 镜像搭建 Web 服务器基于自定义 Python 脚本的 Web 服务器 优化 Docker Web 服务器 绑定数据卷实现动态更新配置环境变量增强灵活性实现负载均衡与扩展性 部署 Docker Web 服务器的实…