了解编程竞赛的复杂性

通常,在各种站点上进行竞争性编程问题时,面临的最困难的任务是以所需的复杂度编写代码,否则程序将获得TLE(超过时限)。天真的解决方案几乎永远不会被接受。那么如何知道什么复杂度是可以接受的呢?

这个问题的答案与在一秒钟内可以执行的操作数直接相关。如今,大多数站点允许每秒108次操作,只有少数站点仍然允许107次操作。在确定可以执行的操作数量之后,通过查看问题中给出的约束条件来寻找合适的复杂性。

例如:给定一个数组A []和一个数字x,请在A []中检查总和为x的一对。

其中N是:

1) 1 <= N <= 103
2) 1 <= N <= 105
3) 1 <= N <= 108

对于案例1

一个天真的解决方案是使用两个for循环工作,因为它给我们一个复杂的O(N2),即使在最坏的情况下,将执行106个操作,远远低于108。当然,在这种情况下,O(N)和O(NlogN)也是可以接受的。

对于案例2

我们必须考虑一个比O(N2)更好的解决方案,因为在最坏的情况下,它将执行1010个操作,因为N是105。因此,对于这种情况,可以接受的复杂性是O(nLogn),它是在108或O(n)下约106(105×10)的操作。

对于案例3

即使是O(NlogN)也给我们提供了TLE,因为它执行了约109次操作,超过108次。所以唯一可以接受的解决方案是O(N),在最坏的情况下,它将执行10^8个操作。

可以在以下网址找到针对这个问题的代码:https://www.geeksforgeeks.org/write-a-c-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-not-there-exist-two-elements-in-s-whose-sum-is-exactly-x/

六一编程网

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Next Post

如何在Python中创建和使用字典

周一 2月 24 , 2020
使用Python,创建和使用字典(dictionary)与处理列表(list)非常相似,除了必须定义 […]