Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

原来最好的算法,就是使用分治思想的经典第k元素算法

Posted by hyerty at 2009-08-21 11:32:14 on Problem 2104
1. 排序,6000ms+,时间复杂度高,算法复杂度低,推荐。
2. 线段树+二分,2000ms,时间复杂度中,算法复杂度高,不推荐。
3. 经典第k元素算法,500ms-,时间复杂度低,算法复杂度中,推荐。

说说第3种算法。想了几天,终于领悟了所谓的 n*log(n) 复杂度算法,原来就是经典的第k元素算法的分治思想:查找一个序列的第k元素,先将其划分为两个子序列,判断第k元素在那个子序列中,转入相应子序列查找,故一次查找复杂度为log(n)。但要先构建划分树,每一次查找,通过查询划分树能在常数时间内决定第k元素在哪个划分第几个元素。这棵划分树非常类似于第二种算法使用的归并树。生成划分树时间复杂度 n*log(n),所以总复杂度为 n * log(n) + m * log(n) = n * log(n)。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator