算法的复杂度

根据算法所需的相对时间量或相对空间量对算法进行分类, 并指定时间/空间需求量随输入大小的变化而变化, 非常方便。

  1. 时间复杂度:程序的运行时间取决于输入大小。
  2. 空间复杂度:某些形式的分析可以根据算法完成任务所需的空间来完成。在计算机存储空间有限的早期计算中, 这种空间复杂性分析至关重要。在考虑此算法时, 分为需要额外空间来完成其工作的算法和需要就地工作的算法。
【算法的复杂度】但是如今, 由于计算机上(内部或外部)的空间已足够, 一天的空间问题很少发生。
大致而言, 我们实现了以下类型的分析-
  • 最坏情况:f(n)由在大小为n的任何实例上执行的最大步数定义。
  • 最佳情况:f(n)由在大小为n的任何实例上执行的最小步骤数定义。
  • 平均情况:f(n)由在大小为n的任何实例上执行的平均步数定义。

    推荐阅读