Блог

Я пытался найти сложность этого алгоритма, и правильно ли я говорю, что сложность равна O (N * log (N))

Может кто-нибудь показать мне полную работу над сложностью этого алгоритма?

 def binary_min(arr):
    if len(arr) == 1:
        return arr[0]
    else:
        mid = len(arr)//2
        min1 = binary_min(arr[0:mid])
        min2 = binary_min(arr[mid:len(arr)])
        if min1 < min2:
            return min1
        else:
            return min2
  

сложность деления на 2 (например, двоичный поиск) log(N) равна, и это будет происходить N раз, поэтому сложность равна Nlog(N)

Предполагая, что это алгоритм бинарного поиска, временная сложность будет O(log n) , а временная сложность в лучшем случае O(1) будет там, где mid индекс соответствует желаемому значению.