[已解决]时间复杂度问题

猪猪虾

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

最佳答案

月排行榜 / 总排行榜

isdkz

2023-4-4 19:22:25

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

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

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

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

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

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

跳转到最佳答案楼层

猪猪虾

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

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

猪猪虾

帖子删不掉，打扰了

isdkz

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

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

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

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

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

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

sfqxx

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

沙漠之烟

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

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

sfqxx

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

我觉得他不会

沙漠之烟

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

emmm人家20年的比你还早

sfqxx

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

emmm好吧

zhangjinxuan

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

sfqxx

复杂