1

因此，在列表中找到最大元素需要 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))))))

这真的更快吗？！你会说渐近时间复杂度是什么（紧界）？

4

1 回答 1

13

给定一个你一无所知的数据列表，如果不检查每个元素，就无法找到最大元素，因此需要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。现在是的，但它仍然cons是O(1)系统要执行的另一项操作。它要求系统分配和释放内存（必须启动垃圾收集器）。真正跳出来的第二件事是，您基本上是在运行合并排序，除了抓取列表的下半部分和上半部分之外，您正在抓取偶数和奇数节点（这也将花费更长的时间，因为您必须迭代每个是时候建立列表了）。您在这里拥有的O(n log n)充其量是一种算法（请注意，它是合并排序，非常适合排序），但它会带来很多额外的开销。

于 2012-02-15T08:13:46.260 回答