算法复杂度和大O表示法

让我们讨论算法的复杂性,尤其是我们如何在算法的上下文中对其进行度量。

给定要解决的相同问题和相同的输入,不同的算法需要花费不同的时间来解决问题。

有时,时间会截然不同,尤其是随着他们需要管理的元素数量的增长。

这种复杂性称为大O,没有其他原因,我们使用大写字母o约定:O(n)O(1)等等。

您将看到的Big O最受欢迎的衡量标准是,按效率高低排序:

  • O(1)
  • O(log n)
  • O(n)
  • O(n * log n)
  • O(n^2)
  • O(n!)

在哪里n是输入的数量。例如,如果您需要对2个项目进行排序n是2,如果您需要分类20.000个项目,n是20.000。

但是,您无需替换其中的值O()计算。这是一个符号,表示开发人员和所有关注算法效率的人。

一种算法O(1)效率是我们所能找到的最好的方法。执行时间不取决于输入的数量,它总是需要相同的时间来执行

一种算法O(n)线性地输入的数量。如果包含10个项目,则需要1秒,而包含100个项目,则需要10秒。

一种算法O(n^2),如果包含4个项目需要16秒,而包含10个项目则需要100秒。

在下一课中,我们将分析和计算大量算法的Big O效率。

重要的是要注意,Big O标记不能提供我们判断一种算法是否比另一种算法更快所需的所有信息,尤其是当它们的Big O值相同时。在这种情况下,您将需要使用其他工具来测试效率。

但是,当算法具有不同的类时(O(n)O(n^2)例如),毫无疑问。