更好更快的方案功能？

Question

因此，找到列表中的最大元素需要 O(n) 时间复杂度（如果列表有 n 个元素）。我尝试实现一种看起来更快的算法。

(define (clever-max lst)
  (define (odd-half a-list)
    (cond ((null? a-list) (list))
          ((null? (cdr a-list))
           (cons (car a-list) (list)))
          (else
           (cons (car a-list)
                 (odd-half (cdr (cdr a-list)))))))
  (define (even-half a-list)
    (if (null? a-list)
        (list)
        (odd-half (cdr a-list))))
  (cond ((null? lst) (error "no elements in list!"))
        ((null? (cdr lst)) (car lst))
        (else
         (let ((l1 (even-half lst))
               (l2 (odd-half lst)))
           (max (clever-max l1) (clever-max l2))))))

这实际上更快吗？你认为渐近时间复杂度是多少（紧界）？

Answer 1

给定一个您一无所知的数据列表，如果不检查每个元素就无法找到最大元素，因此需要 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

即使在这个水平上，我们也正在谈论经济大幅放缓。一旦方法减慢到算法的 10k 评估，就需要增加到大约 100 万个项目，然后直接检查每个项目。

 (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 是O(1)，但它仍然是系统要执行的另一个操作。并且它需要系统分配和释放内存（必须启动垃圾收集器）。真正跳出来的第二件事是，您基本上正在运行合并排序，除了不仅仅抓取列表的下半部分和上半部分，您还抓取偶数和奇数节点（这也将花费更长的时间，因为您必须迭代每个是时候建立列表了）。这里最多是一个 O(n log n) 算法（请注意，它是合并排序，非常适合排序），但它会带来很多额外的开销。