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

Re:你AC程序现在一样可以AC,但是相差常数量级的程序在时间上相差这么多实在是令我很意外！

Posted by Ma6Jia at 2006-12-12 12:25:13 on Problem 1159
In Reply To:两个代码，用的都是DP，只是运算顺序不同，结果一个AC一个TLE Posted by:linandmin at 2006-07-29 23:25:05 
我用了十几个TLE来测试个各种版本的空间复杂度为O(n^2)的代码，始终找不到原因所在，但是所有超时的代码在内层第二个loop除都是有代数运算的，而AC的此类代码则没有运算，而是通过比较跳过了循环；从道理上说，这样的代码差距应该是很小的常数时间，但事实上差距不是我可以想象的。也许我的测试并不能说明什么，或者根本就有问题，但是在这里贴出这些想法是想获得一些帮助，无论如何我真地想知道为什么！

ps:空间复杂度为O(N)的算法，也AC过了，在这里先不提他，因为这些代码，没有此类问题。
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