1.2 算法和算法评价

server/2024/12/2 7:43:05/

1.2.1 算法的基本概念

算法:对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。

算法的五个重要特性

“好”的算法的五个目标

1.2.2 算法效率的度量

一、时间复杂度

算法的时间复杂度是指一个算法每行语句执行次数的最大值。

例子

运行结果

我们可以看到最终的运行次数取决于循环语句的运行次数,而循环语句的执行次数又与n有关,如果n的值无限大,那么循环的运行次数就会无限大,也就是n,所以运行时间复杂度就是n。

例子源代码(C语言)

#include <stdio.h>int main()
{//初始化;int i = 0;//运行了1次!//定义n的值;int n = 10;//运行了1次!//定义循环;for (i = 1; i <= n; i++)//运行了11次!{//打印现在是第几次运行;printf("现在是第%d次运行!", i);//运行了10次!//换行;printf("\n");//运行了10次!}//换行;printf("\n");//运行了1次!//打印总共运行了几次;printf("总共运行了%d次!", i);//运行了1次!return 0;
}

(一)时间复杂度的分类

1.常数阶O(1)

无伦代码执行了多少行,只要没有循环时间复杂度就为O(1)

2.线性阶O(n)

有循环,循环的时间复杂度为O(n)

3.对数阶O(logN)

从上面的代码中可以看到每次i的变化是乘2,所以相当于i乘2的x次方等于n,所以x等于log₂n。

所以时间复杂度为O(log₂n)

4.线性对数阶O(nlog₂n)

就是把对数阶循环n遍,时间复杂度就是O(nlog₂n)。

5.平方阶O(n²)

就是把循环n次再循环n次,时间复杂度为O(n²)。

6.立方阶O(n³)、K次方阶O(n^k)

参考上面的O(n²) 去理解就好了,O(n³)相当于三层n循环,其它的类似。

(二)循环语句的运算方法

以下面的代码为例

运算步骤

①找循环条件:n>=i*i;

②找循环体中的趋近条件结束变量:x=x+1;

③假设循环执行t次;

④将③带入②,计算t<=n的表达式;

       ③带入②:x=t

       ②带入①:n>=t²

                         n½>=t

                         t<=n½

算法的时间复杂度T(n)=O(n½)

(三)时间复杂度的不同情况

最坏时间度复杂度:在最坏的情况下算法的时间复杂度;

(比如找找一个数据,最坏情况就是把所有数据都查完了最后一个才是要找的数据)

平均时间复杂度:所有可能输入实例在等概率情况下,算法的期望运行时间;

(比如找找一个数据,平均情况就是在所有数据中位于中间位置的就是要查找的数据)

最好时间复杂度:在最好情况下算法的时间复杂度;

(比如找找一个数据,最好情况就是把第一个数据就是要查找的数据)

(四)常见的渐进时间复杂度

O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

二、空间复杂度

算法的空间复杂度为该算法在运行过程中所需要的存储空间。

(一)算法空间复杂度O(1)

如果算法执行所需要的临时空间不随着某个变量的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)。

(二)算法空间复杂度O(n)

在上面的代码中数组a需要开辟的存储空间为n,在运行过程中循环只是往开辟好空间的数组a中不断填入数据,所以空间复杂度为O(n)。


http://www.ppmy.cn/server/146654.html

相关文章

MySQL、Oracle、SQL Server 和 PostgreSQL 的分页查询

在不同的数据库中&#xff0c;分页查询是常见的操作&#xff0c;用于从大量数据中获取部分数据集。不同的数据库有不同的分页实现方式。下面是 MySQL、Oracle、SQL Server 和 PostgreSQL 的分页查询语法介绍。 1. MySQL 分页 在 MySQL 中&#xff0c;可以使用 LIMIT 和 OFFSE…

开源 - Ideal库 - Excel帮助类,设计思路(一)

今天开始和大家分享关于Excel最长常用操作封装。 01、起因 市面上有很多Excel操作库&#xff0c;这些库设计之初的目标是提供对Excel的各种操作功能&#xff0c;包括数据、样式、公式、图表等等。而对于我们平时开发来说&#xff0c;大多时候并不需要那么多强大的功能&#xf…

java 接口防抖

防抖&#xff1a;防止重复提交 在Web系统中&#xff0c;表单提交是一个非常常见的功能&#xff0c;如果不加控制&#xff0c;容易因为用户的误操作或网络延迟导致同一请求被发送多次&#xff0c;进而生成重复的数据记录。要针对用户的误操作&#xff0c;前端通常会实现按钮的l…

【西瓜书】支持向量机(SVM)

支持向量机&#xff08;Support Vector Machine&#xff0c;简称SVM&#xff09;。 超平面 分类学习最基本的想法就是基于训练集合D在样本空间中找到一个划分超平面&#xff0c;将不同类别的样本分开。 但能将训练样本分开的划分超平面可能有很多&#xff0c;应该努力去找到哪…

当新能源遇见低空经济:无人机在光伏领域的创新应用

随着全球能源结构的转型和技术的不断进步&#xff0c;新能源行业已成为推动经济社会发展的重要力量。其中&#xff0c;低空经济作为新兴的战略性产业&#xff0c;正深刻改变着人类社会的出行方式和产业链格局。在这一背景下&#xff0c;无人机与光伏产业的结合&#xff0c;不仅…

.net core 创建linux服务,并实现服务的自我更新

目录 创建服务创建另一个服务&#xff0c;用于执行更新操作给你的用户配置一些systemctl命令权限 创建服务 /etc/systemd/system下新建服务配置文件&#xff1a;yourapp.service&#xff0c;内容如下&#xff1a; [Unit] Descriptionyourapp Afternetwork.target[Service] Ty…

Spring Boot优雅读取配置信息 @EnableConfigurationProperties

很多时候我们需要将一些常用的配置信息比如oss等相关配置信息放到配置文件中。常用的有以下几种&#xff0c;相信大家比较熟悉&#xff1a; 1、Value(“${property}”) 读取比较简单的配置信息&#xff1a; 2、ConfigurationProperties(prefix “property”)读取配置信息并与 …

嵌入式Linux中常用的文件系统类型

嵌入式Linux系统中使用的文件系统类型多种多样&#xff0c;每种都有其特点和适用场景。以下是几种常见的嵌入式Linux文件系统类型及其特性&#xff1a; 只读压缩文件系统 SquashFS&#xff1a;一种高度压缩的只读文件系统&#xff0c;适合用于固件映像&#xff0c;它能够提供高…