以下解决方案的时间复杂度是 O(N) 吗？

Question

我试着计算函数的时间复杂度"twoSum"并写下每行的成本和它执行的次数。最后，我制作了两个向量：一个用于成本，另一个用于频率，然后计算它们的内积。我得到以下信息：(n + n + nlogn + n + n + nlogn + n + n + n + n) = 9n + 2logn >> 9n 占主导地位，所以时间复杂度是 O(n)。如果我错了请纠正我！

class Solution(object):

    def binarySearch(self,arr, l, r, x): 
    if r >= l: 
        mid = l + (r - l)/2
        if arr[mid] == x: return mid 
        elif arr[mid] > x:return self.binarySearch(arr, l, mid-1, x)  
        else: return self.binarySearch(arr, mid + 1, r, x) 
    else:return -1

    def twoSum(self, nums, target):
    temp = [i for i in nums] # o(n) 1 time
    nums = list(set(nums)) # o(n) 1 time
    nums.sort() # o(nlogn) 1 time
    for i in range(len(nums)): # o(n) 1 time 
        s = target - nums[i] #  o(1) n times 
        idx_binary = self.binarySearch(nums, 0, len(nums)-1, s) # o(logn) > n times 
        if idx_binary > -1: # o(1) n times 
                idx = temp.index(s, temp.index(nums[i])+1) # o(n) > 1 time
                return [temp.index(nums[i]), idx] # o(n) > 1 time
            else:
                return [temp.index(nums[i]), temp.index(s)] # o(n) > 1 time

Answer 1

你的化简有误，应该是9n + 2nlogn，其中nlogn占优，所以答案是O(nlogn)

以下解决方案的时间复杂度是 O(N) 吗？

is the following solutions' time complexity O(N)?

python

algorithm

time

complexity-theory

big-o