Нахождение сложность моего кода

Question

Я пытаюсь решить вопрос следующий вопрос, взятый из 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) сложность

Answer 1

Это решение действительно O(n).

Прежде всего обратите внимание, что предложение if в основном цикле происходит не более n раз (самое большее один раз за значение i).

Кроме того, также возникает статья elseO(n), так как если значение уже находится в своем положении, вы никогда не меняете свое местоположение снова (гарантируется из условия if).

Таким образом, в главном цикле, есть в большинстве n записей в пункт if, и в большинстве n записей в пункт else, что дают нам общее время работы O(n) для этого цикла.

Второй цикл (который не вложен в первом), является O(n), так что общая сложность O(n)