认识达内从这里开始

认真做教育专心促就业

南宁达内IT培训班算法复杂度概念与计算方法分享

发布：南宁达内it培训
来源：互联网
时间：2023-08-31 09:53

我们在前几期的文章中给大家简单介绍了java程序员入门需要掌握的一些算法基础知识等内容，而本文我们就继续来了解一下，算法复杂度概念与计算方法分享。

南宁达内IT培训班算法复杂度概念与计算方法分享

1、什么是时间复杂度?如何计算?

时间复杂度是衡量算法时间效率的度量标准，通常用大O符号(O)表示。它描述了算法的运行时间与问题规模之间的关系。当问题规模变大时，时间复杂度主要考虑的是算法执行次数的增长率。比如，当问题规模增加k倍时，若算法的执行次数也增加了k倍，则该算法的时间复杂度为O(k)。

时间复杂度的计算主要从算法的基本操作出发，通过估算算法的执行次数，得出差情况下的大O估计。基本操作是指算法中执行次数多，能反映运行时间的操作，通常是算术运算、比较运算、赋值、数组下标访问等。

根据伪代码中的循环和条件语句，我们可以计算出每个基本操作在差情况下执行的次数，从而得出算法的时间复杂度：

外层循环执行n-1次。基本操作为赋值语句，执行次数为n-1次。

内层循环执行(n-1)*n/2次。基本操作为比较和赋值语句，执行次数多为(n-1)*n/2次。

条件语句执行的次数等于内层循环执行的次数。

Swap函数执行的次数多为n-1次。

因此，差情况下该算法的时间复杂度为O(n^2)。

从这个例子可以看出，时间复杂度是对算法执行次数的一种估计，它与具体的机器、编程语言和编译器无关。只要问题规模(即问题的输入数据)足够大，时间复杂度就可以很好地反映出算法的效率。

2、什么是空间复杂度?如何计算?

空间复杂度是衡量算法空间效率的度量标准，通常也用大O符号(O)表示。它描述了算法所需的额外空间(即除了输入数据占用的空间之外的空间)与问题规模之间的关系。当问题规模变大时，空间复杂度主要考虑的是算法所需的额外空间与问题规模的增长率。比如，当问题规模增加k倍时，若算法所需的额外空间也增加了k倍，则该算法的空间复杂度为O(k)。

空间复杂度的计算主要从算法所需的额外空间出发，通过估算算法所需的大额外空间，得出差情况下的大O估计。计算时通常会考虑算法中使用的变量、数组和递归调用所需的栈空间等。

根据伪代码中的数组、变量和递归调用语句，我们可以计算出算法在差情况下所需的大额外空间，从而得出算法的空间复杂度：

归并函数中使用了两个大小为n/2的临时数组left和right，因此大额外空间为O(n)。

MergeSort函数的递归调用栈深度为O(logn)，因为每次递归调用都会把输入数据的规模缩小一半，因此大额外空间也为O(logn)。

因此，差情况下该算法的空间复杂度为O(n)，取两者的较大值。

从这个例子可以看出，空间复杂度是对算法所需的额外空间的一种估计，它与具体的机器、编程语言和编译器有关。只要问题规模不断增大，空间复杂度就可以很好地反映出算法的效率。

【免责声明】本文系本网编辑部分转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!请读者仅作参考。更多内容请加抖音太原达内IT培训学习了解。

< 上一篇：南宁达内java培训班算法复杂度分析方法与原因

下一篇：南宁达内IT培训班Python编程中的运算符都有哪些类型 >