> 我用了十几个TLE来测试个各种版本的空间复杂度为O(n^2)的代码，始终找不到原因所在，但是所有超时的代码在内层第二个loop除都是有代数运算的，而AC的此类代码则没有运算，而是通过比较跳过了循环；从道理上说，这样的代码差距应该是很小的常数时间，但事实上差距不是我可以想象的。也许我的测试并不能说明什么，或者根本就有问题，但是在这里贴出这些想法是想获得一些帮助，无论如何我真地想知道为什么！
> 
> ps:空间复杂度为O(N)的算法，也AC过了，在这里先不提他，因为这些代码，没有此类问题。


另外在以行优先存储的上三角矩阵中，从右下角开始按照行计算，或者从左上角开始按列计算都要比按对角线计算快很多，求其原因可能与O(N^2)这样大的存储空间下访存的具体情况有关！

• Re:你AC程序现在一样可以AC,但是相差常数量级的程序在时间上相差这么多实在是令我很意外！ (105) cgp2001 2007-05-22 23:30:16