python - 发现我的代码的复杂性

我试图解决以下问题，这个问题来自leetcode（https://leetcode.com/problems/first-missing-positive/）
给定一个未排序的整数数组，查找第一个缺少的正整数。
例如，
给定[1,2,0]返回3，
[3,4，-1,1]返回2。
你的算法应该在o（n）时间内运行，并使用常量空间。

class Solution(object):
    def firstMissingPositive(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
        for i in range(len(nums)):
            while nums[i] != i+1:
                if nums[i]<=0 or nums[i]>len(nums) or nums[i]==nums[nums[i]-1]:
                    break
                else:
                    temp=nums[nums[i]-1]
                    nums[nums[i]-1]=nums[i]
                    nums[i]=temp
        for i in range(len(nums)):
           if nums[i]!=i+1:
               return i+1
        return len(nums)+1
b=Solution()
print b.firstMissingPositive([1,1])

我相信这个解决方案具有O（n ^ 2）的复杂性。但仍有许多在线解决方案使用了相同的算法。
谁能解释这个代码是如何具有O（n）复杂度的？

最佳答案

这个解决方案确实是O(n)。
首先，注意主循环中的if子句最多发生n次（每个i值最多发生一次）。
此外，else子句也会发生O(n)次，因为如果一个值已经在其位置上，则永远不会再更改其位置（由if条件保证）。
因此，在主循环中，n子句最多有if个条目，n子句最多有else个条目，这给了我们这个循环的总运行时间O(n)。
第二个循环（不是嵌套在第一个循环中）也是O(n)，所以总的复杂性是O(n)

关于python - 发现我的代码的复杂性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34617740/