算法竞赛中时间复杂度、数据范围与时间限制的关系
有的时候我们在写题的时候总是写完了暴力算法或者其他的,然后提交则TLETLETLE,这是因为我们并没有提前计算好时间复杂度,那可能你会觉得了计算时间复杂度有什么用呢?能知道自己能否通过这时间限制呢?本文就教你怎么判断?首先,我们要知道,在竞赛中,一般认为计算机111秒能执行5×1085×10^85×108次计算,如果题目给出的时间限制为111秒,那么选择的算法执行的计算次数最多应该在10810^8
有的时候我们在写题的时候总是写完了暴力算法或者其他的,然后提交则TLETLETLE,这是因为我们并没有提前计算好时间复杂度,那可能你会觉得了计算时间复杂度有什么用呢?能知道自己能否通过这时间限制呢?本文就教你怎么判断?
首先,我们要知道,在竞赛中,一般认为计算机111秒能执行5×1085×10^85×108次计算,如果题目给出的时间限制为111秒,那么选择的算法执行的计算次数最多应该在10810^8108量级才有可能解决这个题目。
由此,我们则可以得出在一般情况下,时间限制为111秒,时间复杂度和数据范围对应如下:
O(n)O(n)O(n)的算法能解决的数据范围在 n≤108n≤10^8n≤108
O(nlogn)O(nlogn)O(nlogn)的算法能解决的数据范围在 n≤106n≤10^6n≤106
O(nn)O(n\sqrt n)O(nn)的算法能解决的数据范围在 n≤105n≤10^5n≤105
O(n2)O(n^2)O(n2)的算法能解决的数据范围在 n≤5000n≤5000n≤5000
O(n3)O(n^3)O(n3)的算法能解决的数据范围在 n≤300n≤300n≤300
O(2n)O(2^n)O(2n)的算法能解决的数据范围在 n≤25n≤25n≤25
O(n!)O(n!)O(n!)的算法能解决的数据范围在 n≤11n≤11n≤11
当然,这些仅供参考,在一般情况下基本可以得出结果。这样我们在设计算法的时候就可以考虑能不能通过了,不用做无用功甚至交一发TLETLETLE。
更多推荐



所有评论(0)