Мои знания о большом О ограничены, и когда в уравнении появляются логарифмические члены, это меня еще больше сбивает с толку.
Может ли кто-нибудь объяснить мне простым языком, что такое алгоритм O (log n)
? Откуда берется логарифм?
Это специально возникло, когда я пытался решить этот промежуточный практический вопрос:
Пусть X (1..n) и Y (1..n) содержат два списка целых чисел, каждый отсортирован в неубывающем порядке. Приведите алгоритм за время O (log n), чтобы найти медиану (или n-е наименьшее целое число) всех 2n комбинированных элементов. Например, X = (4, 5, 7, 8, 9) и Y = (3, 5, 8, 9, 10), тогда 7 - это медиана объединенного списка (3, 4, 5, 5, 7 , 8, 8, 9, 9, 10). [Подсказка: используйте концепции двоичного поиска]