在分析算法的有效性期间，我有兴趣了解空间和时间以外的参数。例如，我们可以在开发加密算法时专注于有效的陷阱功能。你还能想到什么其他的事情？
问问题
434 次
13 回答
8
首先是正确性。确保您的算法始终有效，无论输入是什么。即使对于算法未设计用于处理的输入，您也应该打印错误消息，而不是使整个应用程序崩溃。如果您使用贪心算法，请确保它们真正适用于每种情况，而不仅仅是您手动尝试的少数情况。
然后是实际效率。在实践中，O(N 2 ) 算法可能比 O(N) 算法快很多。做实际测试，不要过分依赖理论结果。
然后是易于实施。您通常不需要最好的介绍排序实现来对 100 个整数的数组进行一次排序，所以不要打扰。
在你的算法中寻找最坏的情况，如果可能的话，尽量避免它们。如果您有一个通常快速的算法但有一个非常糟糕的最坏情况，请考虑检测最坏情况并使用另一种算法解决它，该算法通常更慢但更适合该单一情况。
考虑空间和时间的权衡。如果您可以负担得起内存以获得更好的速度，那么可能没有理由不这样做，尤其是在您确实需要速度的情况下。如果您买不起内存但可以负担得起更慢的速度，那就这样做。
如果可以，请使用现有库。例如，如果您可以使用 GMP，请不要推出您自己的多精度库。对于 C++，诸如 boost 甚至 STL 容器和算法之类的东西已经由一大群人研究了多年，而且很可能比你一个人做的更好。
于 2010-03-08T14:56:22.217 回答
6
稳定性（排序） ——算法是否保持相等元素的相对顺序？
数值稳定性- 当使用非常大或非常小的实数时，算法是否容易出错？
正确性——算法总是给出正确的答案吗？如果不是，误差范围是多少？
通用性 - 该算法是否适用于许多情况（例如，具有许多不同的数据类型）？
紧凑性——算法的程序是否简洁？
并行性——当并发执行线程的数量增加时，性能的扩展性如何？
Cache Awareness - 该算法是否旨在最大限度地利用计算机的缓存？
Cache Obliviousness - 算法是否针对特定的缓存大小/缓存行大小进行了调整，或者无论缓存的参数如何，它都表现良好？
于 2010-03-08T16:36:42.313 回答
5
稳定性- 某些算法可能会在某些测试条件下“崩溃”，例如执行时间过长，或使用过大的内存量，甚至可能不会终止。
于 2010-03-08T14:50:53.540 回答
5
复杂。2 算法在所有其他方面都相同，更简单的算法将成为未来定制和使用的更好候选者。
易于并行化。根据您的用例，它可能没有任何区别，或者另一方面，使算法无用，因为它不能使用 10000 个内核。
于 2010-03-08T14:53:15.933 回答
4
功耗，用于嵌入式算法（想想智能卡）。
于 2010-03-08T15:14:11.750 回答
4
对于执行浮点运算的算法，舍入误差的累积通常是一个考虑因素。
于 2010-03-08T15:07:48.920 回答
3
在算法分析中经常测量的一个重要参数是缓存命中和缓存未命中。虽然这是一个非常依赖于实现和架构的问题，但可以在某种程度上进行概括。该算法的一个特别有趣的特性是 Cache-oblivious，这意味着该算法将在具有不同缓存大小和结构的多台机器上优化使用缓存而无需修改。
于 2010-03-08T14:54:38.133 回答
3
时间和空间是大的，它们看起来如此简单和明确，因此它们通常应该被限定（1）。OP 使用“参数”一词而不是“标准”或“属性”这一事实在某种程度上表明了这一点（好像时间和空间上的大 O 值足以构成基础算法）。
其他标准包括：
- 适用范围
- 复杂
- 数学易处理性
- 结果的确定性
- 易于调整（可能与前面提到的“复杂性”和“可触性”有关）
- 以并行方式运行算法的能力
（1）“合格”：正如其他答案中所暗示的那样，在 90% 的情况下（顺便说一句，可能是 100% 的实际案例）
于 2010-03-08T14:55:29.410 回答
2
如果我们一般谈论算法，那么（在现实世界中）您可能必须考虑 CPU/文件系统（读/写操作）/带宽使用情况。
诚然，它们在你现在需要担心的事情列表中排得很靠后，但是考虑到足够大的数据量和足够便宜的基础设施，你可能需要调整你的代码以缓解其中一个问题。
于 2010-03-08T15:12:14.917 回答
2
最坏情况和最佳情况也很有趣，尤其是在与输入中的某些条件相关联时。如果您的输入数据显示某些属性，则利用此属性的算法可能比执行相同任务但不使用该属性的另一个算法执行得更好。
例如，当输入以特定方式部分排序时，许多排序算法的执行效率非常高，从而最大限度地减少了算法必须执行的操作数量。（如果您的输入大部分已排序，则插入排序将非常适合，否则您将永远不会使用该算法）
于 2010-03-08T14:52:59.927 回答
1
您感兴趣的不是参数，而是算法的内在属性。
无论如何，您可能感兴趣并分析算法的另一个属性涉及启发式（或者更确切地说，近似算法），即没有找到精确解决方案但（希望）足够好的算法。
您可以分析解决方案与最坏情况下的理论最优解决方案的差距。例如，现有算法（忘记了哪一个）将最优旅行商行程近似为两倍，即在最坏的情况下，它是最优行程的两倍。
另一个指标涉及随机算法，其中使用随机化来防止出现不需要的最坏情况行为。一个例子是随机快速排序；快速排序的最坏情况运行时间为O ( n 2 )，这是我们想要避免的。通过预先对数组进行洗牌，我们可以以非常高的概率避免最坏情况（即已经排序的数组）。知道这个概率有多高很重要。这是算法的另一个内在属性，可以使用随机进行分析。
于 2010-03-08T14:54:37.277 回答
1
对于数值算法，还有连续性的性质：即，如果你稍微改变输入，输出也只是轻微改变。另请参阅Lambda The Ultimate上程序的连续性分析以获取讨论和学术论文的链接。
对于惰性语言，也有严格性：f称为严格 if f _|_ = _|_（其中_|_表示底部（在域理论的意义上），由于非终止、错误等而无法产生结果的计算），否则为非-严格的。例如，函数\x -> 5是非严格的，因为(\x -> 5) _|_ = 5, 而是\x -> x + 1严格的。
另一个属性是确定性：算法的结果（或其其他属性，例如运行时间或空间消耗）是否仅取决于其输入。
于 2010-03-08T17:12:03.643 回答
0
其他答案中关于各种算法质量的所有这些事情都很重要，应该加以考虑。
但是时间和空间是与输入（n）的大小相比以某种速率变化的两件事。那么还有什么可以根据 n 变化？
有几个与 I/O 相关。例如，对磁盘的写入次数是一个重要的参数，仅通过空间和时间估计可能无法直接显示。这对于闪存尤为重要，在闪存中，对同一内存位置的写入次数是某些算法中的重要指标。
另一个 I/O 指标是“闲聊”。一个网络协议可能会更频繁地发送较短的消息，从而增加与另一个网络协议相同的空间和时间，但系统的某些方面（可能是计费？）可能会使所需的消息的大小或数量最小化。
这就把我们带到了成本上，这有时是一个非常重要的算法考虑因素。算法的成本可能会受到不同数量的空间和时间的影响（考虑服务器存储空间和千兆数据传输的单独成本），但成本是您希望总体上最小化的东西，所以它可能有它的自己的大 O 估计。
于 2010-03-08T17:57:32.703 回答