数据与结构--时间复杂度和空间复杂度-CSDN博客

　　Func2:

　　这个函数包含一个 循环和一个 循环，它们的迭代次数分别为 2 * N 和 10。因此，时间复杂度为 O(N)。

　　Func3:

　　这个函数包含两个 循环，它们的迭代次数分别为 M 和 N。因此，时间复杂度为 O(M + N)。

　　Func4:

　　这个函数只包含一个固定次数的 循环，其迭代次数是一个常数 100，不受输入参数 N 的影响。因此，时间复杂度为 O(1)。

　　冒泡排序是一种简单直观的排序算法，它重复地遍历要排序的列表，比较相邻的元素并交换它们，如果顺序不正确就交换。重复这个过程直到不需要交换，即列表已经排序完成。现在我们来分析冒泡排序的时间复杂度。

　　假设列表长度为 N。

　　冒泡排序的基本思想是每次从头开始比较相邻的两个元素，如果逆序就交换它们，直到将最大的元素移到列表的末尾。重复这个过程，每次都将当前未排序部分的最大元素交换到未排序部分的最后。所以，冒泡排序的核心是一次遍历会将一个最大（或最小）的元素放到正确的位置上。

　　最坏情况下，需要进行 N-1 轮比较。在每一轮比较中，需要比较的次数都会减少，因为每一轮都会有一个最大（或最小）的元素被放到了正确的位置上。因此，在第一轮中需要比较 N-1 次，第二轮中需要比较 N-2 次，以此类推，直到最后一轮只需要比较 1 次。

　　所以，总的比较次数可以表示为：

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

　　可以看到，上面的代码创建了flag,i,j三个临时变量,用大O表示空间复杂度是O( 1 )

　　需要说明的是，此处的要进行排序的数组array并能计算在空间复杂度里，因为它不是BubbleSort方法临时创建的变量

本文 zblog模板 原创，转载保留链接！网址：https://gulangwanhotelxiamen.com/post/4043.html