大哦符号 [英] Big Oh notation

问题描述

只是需要一些真正的快速确认。 如果一个算法以 N（N-1）/ 2 测试运行，是大哦为O（n ^ 2）？

Just need a confirmation on something real quick. If an algorithm takes n(n-1)/2 tests to run, is the big oh O(n^2)?

推荐答案

N（N-1）/ 2扩展到（N ^ 2 -N）/ 2 ，这是（N ^ 2/2） - （N / 2）

n(n-1)/2 expands to (n^2 -n) / 2, that is (n^2/2) - (n/2)

（N ^ 2/2）和（N / 2）是两个功能的部件，其中 N R个2月2日占主导地位。 因此，我们可以忽略 - 。（N / 2）部分。

(n^2/2) and (n/2) are the two functions components, of which n^2/2 dominates. Therefore, we can ignore the - (n/2) part.

在 N ^ 2/2 您可以安全地删除/ 2部分渐近记法分析。

From n^2/2 you can safely remove the /2 part in asymptotic notation analysis.

这简化了 N ^ 2

所以，是的，它是在为O（n ^ 2）

Therefore yes, it is in O(n^2)

这篇关于大哦符号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！