Думайте об этом как O(n*log(n)), то есть "выполняете log(n) работу n раз".Например, поиск элемента в отсортированном списке длиной n равен O(log(n)).Поиск элемента в n различных отсортированных списках, каждый из которых имеет длину n, равен O(n*log(n)).
. Помните, что O(n) определяется относительно некоторого действительного количества n .Это может быть размер списка или количество различных элементов в коллекции.Поэтому каждая переменная, которая появляется внутри O(...), представляет собой нечто, взаимодействующее для увеличения времени выполнения.O(n*m) может быть написано O(n_1 + n_2 + ... + n_m) и представлять то же самое: «делать n, m раз».
Давайте рассмотрим конкретный пример этого, mergesort.Для n элементов ввода: На самой последней итерации нашего вида у нас есть две половины ввода, каждая половина размера n/2, и каждая половина сортируется.Все, что нам нужно сделать, это объединить их вместе, что занимает n операций.На предпоследней итерации у нас в два раза больше кусков (4) размером n/4.Для каждой из наших двух пар размером n/4 мы объединяем пару вместе, что требует n/2 операций для пары (по одной для каждого элемента в паре, как и раньше), то есть n операций для двух пар.
Отсюда мы можем экстраполировать, что для каждого уровня нашей сортировки слияний требуется n операций для слияния.Следовательно, сложность big-O составляет n раз количество уровней .На последнем уровне размер объединяемых фрагментов равен n/2.До этого это n/4, до этого n/8 и т. Д. До размера 1.Сколько раз вы должны разделить n на 2, чтобы получить 1?log(n).Итак, у нас есть log(n) уровней.Таким образом, наше общее время выполнения составляет O(n (work per level) * log(n) (number of levels)), n работа log(n) раз.