算法的时间复杂度取决于待处理数据的初态，为什么？？待处理数据的初态该怎么理解？

发布网友 发布时间：2022-04-26 23:36

我来回答

共2个回答

热心网友 时间：2023-11-12 08:27

确定的一种算法，对不同的数据集所消耗的时间是不同的，如果初始的数据有一定的特性或规律，可以减少操作的次数，消耗较少的时间。
以冒泡发排序为例，交数组中相邻两个数是基本操作。在极端状态下，如果初始的数据就是按从小到大的顺序排列好的，那么执行基本操作的次数为0，如果初始数据按从大到小的顺序排列，执行基本操作的次数就是n*(n-1)/2。
这样解释是你想问的吗

热心网友 时间：2023-11-12 08:27

从定义上看，用算法中操作执行的次数计算时间复杂度，当然初态不同，执行的次数就不同，所以说与初态有关。
但是，普遍接受的定义是：算法的复杂度是最坏情况（执行次数最多的情况）下按执行次数计算的，如我们说冒泡算法的时间复杂度是O(N2)，而不是说你先给我数据和数据的初态再说算法的时间复杂度。这时候，就与初态无关了。（说明：论文中说算法复杂度一定是这种，国际公认）
具体哪个题目吗，考试绝不能出这样的题目。

热心网友 时间：2023-11-12 08:27

确定的一种算法，对不同的数据集所消耗的时间是不同的，如果初始的数据有一定的特性或规律，可以减少操作的次数，消耗较少的时间。
以冒泡发排序为例，交数组中相邻两个数是基本操作。在极端状态下，如果初始的数据就是按从小到大的顺序排列好的，那么执行基本操作的次数为0，如果初始数据按从大到小的顺序排列，执行基本操作的次数就是n*(n-1)/2。
这样解释是你想问的吗

热心网友 时间：2023-11-12 08:27

从定义上看，用算法中操作执行的次数计算时间复杂度，当然初态不同，执行的次数就不同，所以说与初态有关。
但是，普遍接受的定义是：算法的复杂度是最坏情况（执行次数最多的情况）下按执行次数计算的，如我们说冒泡算法的时间复杂度是O(N2)，而不是说你先给我数据和数据的初态再说算法的时间复杂度。这时候，就与初态无关了。（说明：论文中说算法复杂度一定是这种，国际公认）
具体哪个题目吗，考试绝不能出这样的题目。