发现我的代码的复杂性

Question

我正在尝试解决以下问题，该问题取自 leetcode(https://leetcode.com/problems/first-missing-positive/)

给定一个未排序的整数数组，找到第一个缺失的正整数。

例如，给定 [1,2,0] return 3，和 [3,4,-1,1] return 2.

您的算法应该在 O(n) 时间内运行并使用常量 space。

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)

Answer 1

这个解决方案确实O(n).

首先，请注意主循环中的 if 子句最多发生 n 次（每个 i 的值最多发生一次）。

此外，else 子句也出现了 O(n) 次，因为如果一个值已经在它的位置上，你就永远不会再改变它的位置（由 if 条件保证）。

因此，在主循环中，if 子句最多有 n 个条目，else 子句最多有 n 个条目，给出此循环的总运行时间 O(n)。

第二个循环（未嵌套在第一个循环中）也是 O(n)，因此总复杂度为 O(n)

发现我的代码的复杂性

Finding complexity of my Code

python

algorithm

big-o

time-complexity