Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

用quick sort老是TLE, 见过各位讨论, 改用heap sort, AC 了: 2096K 765MS

Posted by Lucas at 2005-03-13 00:02:46 on Problem 1002

quick sort:
  平均情况:
      比较次数:  1.39 n lg n + O(n)
      交换次数:  0.69 n lg n + O(n)
  最坏情况:
      O(n^2) 出现灾难!!!

heap sort:
  最坏情况:
      比较次数:  比quick sort的平均情况稍差一点
      交换次数:  比quick sort的平均情况稍好一点

Followed by:

Post your reply here:

Home Page Go Back To top