首页 > 编程语言 >算法的时间复杂度和空间复杂度

算法的时间复杂度和空间复杂度

时间:2024-11-03 09:16:19浏览次数:6  
标签:arr int 复杂度 算法 时间 空间

目录

1.算法的复杂度

2.时间复杂度

2.1时间复杂度的概念

2.2大O的渐进表示法

3.空间复杂度


1.算法的复杂度

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

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

2.时间复杂度

2.1时间复杂度的概念

时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数(这里的函数不是指C语言中的函数,而是数学上含有未知量的函数),它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个

分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。

即:找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度。

另外,环境不同,代码的具体运行时间也不同

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

2.2大O的渐进表示法

大o符号(Big O notation):是用于描述函数渐进行为的数学符号。

推导大O阶方法:

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

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

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

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

O(N^2)

. N= 10 F(N) = 100

. N = 100 F(N) = 10000

. N = 1000 F(N) = 1000000

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。

另外有些算法的时间复杂度存在最好、平均和最坏情况:

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

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

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

例如:在一个长度为N数组中搜票一个数据x

最好情况:1次找到

最坏情况:N次找到

平均情况:N/2次找到

在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

等比数列求和公式

3.空间复杂度

空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度。

空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。

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

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

void find_num(const void* e1, const void* e2)
{
	return (*(int*)e1) - (*(int*)e2);
}

//思路1
int main()
{
	int ret = -1;
	int arr[8] = { 0,6,2,5,1,4,7,8 };
	qsort(arr, 8, sizeof(arr[0]), find_num);
	for (int i = 0; i < 8; i++)
	{
		if (arr[i] != i)
		{
			ret = i;
			break;
		}
	}
	printf("%d", ret);
	return 0;
}
//思路2
int main()
{
	int ret1 = 0;
	int ret2 = 0;
	int arr[8] = { 0,6,2,5,1,4,7,8 };

	for (int i = 0; i <= 8; i++)
	{
		ret1 += i;
	}

	for (int i = 0; i < 8; i++)
	{
		ret2 += arr[i];
	}
	printf("%d\n", ret1 - ret2);
	return 0;
}
int find_num(int* nums, int numsizes)
{
	int x = 0;
	//先和0到n异或
	for (int i = 0; i <= numsizes; i++)
	{
		x ^= i;
	}
	//再和数组的数异或
	for (int i = 0; i < numsizes; i++)
	{
		x ^= nums[i];
	}
	return x;
}

//思路4
int main()
{
	int arr[8] = { 3,1,6,4,5,2,8,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int ret = find_num(arr, sz);
	printf("%d\n", ret);
	return 0;
}

void reverse(int* arr, int left, int right)
{
	while (left < right)
	{
		int temp = arr[left];
		arr[left] = arr[right];
		arr[right] = temp;

		left++;
		right--;
	}
}

int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int k = 0;
	scanf("%d", &k);
	if (k >= 10)
		k %= 10;
	reverse(arr, 0, k - 1);
	reverse(arr, k, 9);
	reverse(arr, 0, 9);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}

标签:arr,int,复杂度,算法,时间,空间
From: https://blog.csdn.net/2402_83411382/article/details/143461046

相关文章

  • 基于django框架在线图书推荐系统的设计与实现 python个性化图书/书籍/电子书推荐系统
    基于django框架在线图书推荐系统的设计与实现python个性化图书/书籍/电子书推荐系统平均加权混合推荐热门推荐协同过滤算法推荐爬虫排行榜数据可视化分析机器学习深度学习大数据一、项目简介1、开发工具和使用技术Pycharm、Python3及以上版本,Django3.6及以上版......
  • 计算机视觉的研究方向和相应算法
    计算机视觉是一个广泛的领域,涵盖了多种研究方向和算法。以下是对计算机视觉研究方向及其相关算法的详细介绍:研究方向图像识别与分类:研究如何让计算机识别并分类图像中的对象,如车辆、人脸、动物等。目标检测与跟踪:研究如何让计算机在图像或视频中检测并跟踪特定的目标对象......
  • 记录一下自己的优化字符串匹配算法
    我愿称之KeBF算法Ke的BF(BruteForce,暴力检索)法关于其他字符串匹配算法示例源码#include<stdio.h>#include<string.h>intmain(){//读入两个字符串charms[100],ps[100];fgets(ms,sizeof(ms),stdin);fgets(ps,sizeof(ps),stdin);//......
  • 深度讲解-互联网算法备案指南和教程
    随着人工智能和大数据技术的迅猛发展,互联网算法在内容推荐、用户画像、智能客服等领域发挥着越来越重要的作用。然而,算法的广泛应用也带来了潜在的安全风险和合规挑战。为了规范互联网算法的开发与应用,国家互联网信息办公室等相关部门发布了《互联网算法备案管理规定》,要求具备......
  • 代码随想录算法训练营第十天|leetcode232.用栈实现队列、leetcode225. 用队列实现栈、
    1leetcode232.用栈实现队列题目链接:232.用栈实现队列-力扣(LeetCode)文章链接:代码随想录视频链接:栈的基本操作!|LeetCode:232.用栈实现队列哔哩哔哩bilibili自己的思路:真的第一次接触这个概念,完全没有任何思路,甚至不知道从何下手1.1基本概念栈就是相当于砌墙的砖头,先......
  • 代码随想录算法训练营第九天|leetcode151.翻转字符串里的单词、卡码网55.右旋字符串、
    1leetcode151.翻转字符串里的单词题目链接:151.反转字符串中的单词-力扣(LeetCode)文章链接:代码随想录视频链接:字符串复杂操作拿捏了!|LeetCode:151.翻转字符串里的单词哔哩哔哩bilibili自己的思路:直接将空格去掉,然后分割字符串为列表,在列表中进行翻转,不在字符串内部操作......
  • C++优选算法 分治-快排
    一、基本思想快速排序采用分治法策略,将一个大数组(或子数组)分为两个小数组,然后递归地对这两个小数组进行排序。其基本思想可以概括为“分解、解决、合并”三个步骤:分解:将原问题(即待排序的数组)分解为若干个规模较小、相互独立且与原问题形式相同的子问题(即子数组)。解决:若子问题......
  • 集智书童 | 利用知识蒸馏算法优化 YOLOv5 目标检测 !
    本文来源公众号“集智书童”,仅用于学术分享,侵权删,干货满满。原文链接:利用知识蒸馏算法优化YOLOv5目标检测!这篇论文探讨了知识蒸馏技术在目标检测任务中的应用,尤其是不同蒸馏温度对学生模型性能的影响。通过将YOLOv5s作为教师网络和较小的YOLOv5s作为学生网络,作者发现,随......
  • tarjan算法
    强连通分量细节对于多点跑tarjan来说,可能会有先访问\(u\tov\)中的\(v\),这导致\(dfn[v]<dfn[x]\),后面\(x\)跑tarjan时会误把\(v\)当成祖先,要加判断割点&割边删去后使图不连通的点/边找割边和强连通分量求法大差不差,这里不再赘述找割点不同于前两者,首先割点不是low[x]==dfn......
  • 【排序算法】堆排序
    ......