时间戳

首页 > 解决方案 > 为什么以下算法（循环排序？！）的时间复杂度是 O(n)？

algorithm - 为什么以下算法（循环排序？！）的时间复杂度是 O(n)？

问题描述

循环排序的时间复杂度是 O(n^2)参考

但是，该解决方案声称以下涉及循环排序的算法仅使用 O(n)。时间复杂度不应该是 O(n^2) 吗？

    def find_all_missing_numbers(nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        i = 0

        # This is cycle sort and should use O(n^2)?!
        while i < len(nums):
            j = nums[i] - 1
            if nums[i] != nums[j]:
                nums[i], nums[j] = nums[j], nums[i]  # swap
            else:
                i += 1

        missingNumbers = []

        # O(n)
        for i in range(len(nums)):
            if nums[i] != i + 1:
                missingNumbers.append(i + 1)

        return missingNumbers
#

时间复杂度 = O(n^2 + n) = O(n^2)。解决方法错了吗？

标签： algorithmsortingtime-complexitycycle-sort

解决方案

这不是循环排序，如果数组由 range 中的数字组成，则该算法旨在查找缺失的数字[1, len(array)]。

print(find_all_missing_numbers([5,4,3,2,1]))
print(find_all_missing_numbers([1,2,3,5,5]))
print(find_all_missing_numbers([2]))

[]
[4]
错误

这一行假设正确的位置是由一个存储的数字给出的，只有当数字在上面显示的范围内时，它才可能有效。

j = nums[i] - 1

而循环排序花费线性时间为每个数字寻找合适的位置。

推荐阅读