Учитывая список данных, о которых вы ничего не знаете, невозможно найти максимальный элемент, не изучив каждый элемент и, таким образом, не потратив O(n) времени, потому что, если вы его не проверите, вы можете его пропустить. Так что нет, ваш алгоритм не быстрее, чем O(n), на самом деле он O(n log n), поскольку вы в основном просто выполняете сортировку слиянием.
Вот еще данные о проблеме выбора
Я подумал об этом и понял, что, вероятно, мне следует сделать что-то большее, чем просто заявить об этом как факт Итак, я написал быстрый тест скорости. Теперь полное раскрытие, я не программист на Scheme, так что это в Common Lisp, но я думаю, что я верно преобразовал ваш алгоритм.
;; Direct "iteration" method -- theoretical O(n)
(defun find-max-001 ( list )
(labels ((fm ( list cur )
(if (null list) cur
(let ((head (car list))
(rest (cdr list)))
(fm rest (if (> head cur) head cur))))))
(fm (cdr list) (car list))))
;; Your proposed method
(defun find-max-002 ( list )
(labels ((odd-half ( list )
(cond ((null list) list)
((null (cdr list)) (list (car list)))
(T (cons (car list) (odd-half (cddr list))))))
(even-half ( list )
(if (null list) list (odd-half (cdr list)))))
(cond ((null list) list)
((null (cdr list)) (car list))
(T (let ((l1 (even-half list))
(l2 (odd-half list)))
(max (find-max-002 l1) (find-max-002 l2)))))))
;; Simplistic speed test
(let ((list (loop for x from 0 to 10000 collect (random 10000))))
(progn
(print "Running find-max-001")
(time (find-max-001 list))
(print "Running find-max-002")
(time (find-max-002 list))))
Теперь вы можете спросить себя, почему вы используете только 10000 для размера списка, потому что на самом деле это довольно мало для асимптотических вычислений. Дело в том, что sbcl признает, что первая функция является хвостовой рекурсивной, и поэтому абстрагирует ее в цикл, тогда как со второй она не делает, так что она настолько велика, насколько я могу получить, не убивая свой стек. Хотя, как видно из приведенных ниже результатов, этого достаточно, чтобы проиллюстрировать это.
"Running find-max-001"
Evaluation took:
0.000 seconds of real time
0.000000 seconds of total run time (0.000000 user, 0.000000 system)
100.00% CPU
128,862 processor cycles
0 bytes consed
"Running find-max-002"
Evaluation took:
0.012 seconds of real time
0.012001 seconds of total run time (0.012001 user, 0.000000 system)
[ Run times consist of 0.008 seconds GC time, and 0.005 seconds non-GC time. ]
100.00% CPU
27,260,311 processor cycles
2,138,112 bytes consed
Даже на этом уровне мы говорим о массовом замедлении. Требуется увеличение примерно до одного миллиона элементов перед прямой проверкой каждого элемента, если метод замедляется до оценки вашего алгоритма на 10 тыс.
(let ((x (loop for x from 0 to 1000000 collect (random 1000000))))
(time (find-max-001 x)))
Evaluation took:
0.007 seconds of real time
0.008000 seconds of total run time (0.008000 user, 0.000000 system)
114.29% CPU
16,817,949 processor cycles
0 bytes consed
Заключительные мысли и выводы
Итак, следующий вопрос, который нужно задать, - почему второй алгоритм действительно занимает намного больше времени. Не вдаваясь в подробности о устранении хвостовой рекурсии , есть несколько вещей, которые действительно выпрыгивают.
Первый из них cons. Да, cons - это O(1), но это еще одна операция для системы. И это требует от системы выделения и освобождения памяти (приходится запускать сборщик мусора). Второе, что действительно бросается в глаза, это то, что вы в основном выполняете сортировку слиянием, за исключением того, что вместо того, чтобы просто захватывать нижнюю и верхнюю половину списка, вы берете четные и нечетные узлы (это также займет больше времени, потому что вам приходится повторять каждый время строить списки). Здесь у вас есть алгоритм O(n log n) в лучшем случае (учтите, это сортировка слиянием, которая действительно хороша для сортировки), но она несет в себе много дополнительных затрат.