寻找良好的奖金测验以测试效率（特别是与时间相关的效率）[关闭

Question

我每周一次对计算机科学实验室进行介绍。我希望在下一个实验室结束时进行快速竞赛。我想给他们一个这样的代码块：

public class EfficientCode{

    public static void main(){
        long startTime, endTime, executionTime;
        startTime = System.currentTimeMillis();

        yourEfficientMethod():
        endTime = System.currentTimeMillis();
        executionTime = endTime – startTime;

    }

    public static void doSomething(){
        // you do this part.  
    }

}

他们将实施滴定方法，而代码最快的人将获得一些奖励标记。

问题在于，这个问题需要有些简单。学生对：循环，如果/其他，弦，添加，阵列等都有一个很好的掌握。

这是我对问题的想法：

• 找到1到100万之间的所有完美数字。 （一个完美的数字是一个数字，所有数字的因素累加到数字中。即：6 = 3 + 2 + 1）
• 查找1至100万之间的所有质数

我认为，为了使方法之间的性能有可衡量的差异，您必须做很多次。

Answer 1

因为这是一个入门班，您的学生还没有介绍整理，我认为很难想出一些简单的事情，很有趣，足以拥有几种不同的方法，并且足够复杂，以至于那里在现代计算机上的不同实现之间的速度是明显的差异。不过，您真正的问题是，任何简单的事情都可以尝试尝试使用规范的实现，只有很短的Google搜索。

我的建议是颠覆挑战。让您的学生竞争，提出他们能想到的最刺耳，最慢，最记忆的解决方案。我认为，思考所有错误的做某事的方式在教育上很有价值，而要思考权利，并且很难成为最好的事情。由于不良代码将是 真的 减缓。也没有谷歌搜索答案。最后，在我（无关）的意见中，这具有使挑战更有趣的额外好处。

诸如在另一个字符串中找到字符串之类的东西更容易做到比好的。也许让他们从2KB的随机字母数字字符串中提取所有质量数。有很多方法可以使猪的耳朵陷入困境。

Answer 2

对于短暂的操作，就“多次”达成了同意，但对于更长的操作，曾经本身就足够了。

我建议调查 Euler项目, ，非常出色的编程问题。最好的部分是，这些问题是考虑到“一分钟规则”的，大多数问题应花费小于一分钟的计算机来执行 高效的 算法找到答案。这是一个很好的起点。 :)

Answer 3

两件事情。

首先，效率大约超过执行时间。它还涉及内存使用情况，内存访问，文件系统/资源访问等。有很多事情可以提高效率。因此，请明确说明您正在寻找最短的运行时间例程。否则您将发送一条混合消息...

其次，大约15年前，我听到了这个问题，我不能忘记它：

产生所有5位数字对的列表 121212. 。但是，两个数字都不能重复小数位数。所以 1 任何一个数字只能出现一次。因此，结果对是 98167 + 23045. 。有一个合理的数字，很容易构建一个蛮力的解决方案，但是有效的解决方案需要一些思考。有192个独特的对...

Answer 4

这些是好主意。有一个分类问题呢？

Answer 5

对数字进行排序也可能是一个好主意，因为所有算法都具有不同的性能特征（插入，选择，快速，快速，堆等）。这也将使学生有机会学习大o符号等。