猪猪虾 发表于 2023-4-4 19:15:09

时间复杂度问题

为什么时间复杂度是n,使用了两次for循环？

猪猪虾 发表于 2023-4-4 19:17:10

我知道了，抱歉，今天是没带脑子

因为不是for循环嵌套，所以是n

猪猪虾 发表于 2023-4-4 19:19:27

本帖最后由 猪猪虾 于 2023-4-4 19:21 编辑

帖子删不掉，打扰了

isdkz 发表于 2023-4-4 19:22:25

虽然这段代码中有两个for循环，但它们的时间复杂度之和仍然是O(n)。

这是因为第一个循环的内部while循环与外部for循环之间存在关联。

具体地说，在while循环中的swap操作会将nums]放到正确的位置。换句话说，元素nums]最多只会被交换一次。

考虑最坏的情况，也就是每个元素都需要被交换一次。那么整个过程中最多会发生n次交换。

所以第一个for循环的时间复杂度为O(n)。而第二个for循环是一个简单的遍历，时间复杂度也为O(n)。

因此，这段代码的总时间复杂度为O(n) + O(n) = O(2n)，在大O表示法中，我们可以去掉常数系数，所以最终时间复杂度为O(n)。

sfqxx 发表于 2023-4-4 19:44:38

请设置最佳答案以便移动到【已经解决】模块

沙漠之烟 发表于 2023-4-4 20:24:09

sfqxx 发表于 2023-4-4 19:44
请设置最佳答案以便移动到【已经解决】模块

不用，只要将帖子模块改为已经解决就行了

sfqxx 发表于 2023-4-4 20:24:34

沙漠之烟 发表于 2023-4-4 20:24
不用，只要将帖子模块改为已经解决就行了

我觉得他不会{:10_266:}

沙漠之烟 发表于 2023-4-4 20:26:29

sfqxx 发表于 2023-4-4 20:24
我觉得他不会

emmm人家20年的比你还早

sfqxx 发表于 2023-4-4 20:31:43

沙漠之烟 发表于 2023-4-4 20:26
emmm人家20年的比你还早

emmm好吧

zhangjinxuan 发表于 2023-4-4 21:19:18

时间复杂度是理性的，不是感性的

sfqxx 发表于 2023-5-4 20:17:30

复杂
页: [1]
查看完整版本: 时间复杂度问题