algorithm - 为什么跟随算法(循环排序!!)的时间复杂度是O(n)？

循环排序的时间复杂度为O（n ^ 2）reference
然而，该解决方案声称以下涉及循环排序的算法仅使用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）。解决方案错了吗？

最佳答案

这不是循环排序，该算法设计用于在数组由[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]))

[]
[四]
错误
这一行假设存储的数字给出了正确的位置，只有当数字在上面所示的范围内时才有效。

j = nums[i] - 1

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

关于algorithm - 为什么跟随算法(循环排序!!)的时间复杂度是O(n)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57764457/