Как вы относитесь к O(n ^ 2)?Лично мне нравится думать об этом как о O(n) работе O(n) раз.
Придуманный алгоритм O(n ^ 2) будет повторять все пары чисел в 0, 1, ..., n - 1
def print_pairs(n):
for i in range(n):
for j in range(i + 1, n):
print('({},{})'.format(i, j))
Используя логику, аналогичную описанной выше, вы могли бы O(log n) работать O(n) раз и иметь временную сложность O(n log n).
В качестве примера, мы собираемся использовать бинарный поиск, чтобы найти всеиндексы элементов в массиве.
Да, я понимаю, что это глупый пример, но здесь я не хочу сосредоточиться на полезности алгоритма, а скорее на сложности.Ради правильности нашего алгоритма предположим, что входной массив отсортирован.В противном случае наш двоичный поиск не будет работать должным образом и может работать бесконечно.
def find_indices(arr):
indices = []
for num in arr:
index = binary_search(arr, 0, len(arr), num)
indices.append(index)
return indices
def binary_search(arr, l, r, x):
# Check base case
if r >= l:
mid = l + (r - l)/2
# If element is present at the middle itself
if arr[mid] == x:
return mid
# If element is smaller than mid, then it
# can only be present in left subarray
elif arr[mid] > x:
return binary_search(arr, l, mid-1, x)
# Else the element can only be present
# in right subarray
else:
return binary_search(arr, mid + 1, r, x)
else:
# Element is not present in the array
return -1
Что касается вашего второго вопроса, то, конечно, log n << n при n стремится к бесконечности, поэтому
O(n + log n) = O(n)
Теоретически, log n затмевается на n, так как мы получаем произвольно большие значения, поэтому мы не включаем его в наш анализ Big O.
Сопоставляется с практикой, гдеВы можете рассмотреть эту дополнительную log n работу, если ваш алгоритм испытывает проблемы с производительностью и / или масштабированием.