文章目录

• 1. 基本概念
• 2. 算法的时间复杂度和空间复杂度
• • 2.1 时间复杂度T(n)=O(f(n))
  • 2.2 算法的空间复杂度S(n)=O(f(n))

1. 基本概念

• 什么是算法？
  算法是解决特定问题的计算方法和步骤。在计算机中为有限序列的指令，每条指令可以表示一个或多个操作。

• 算法的特性：
  （1）算法具有零个或多个输入（零个输入比如打印“Hello World!”），至少有一个输出。
  （2）有穷性：算法的执行步骤是有限的，且每个步骤执行的时间要在可接受的范围内
  （3）确定性：算法的每个步骤都有确定的含义
  （4）可行性：算法的每一步都是可行的，每一步都能通过执行有限次数完成

• 算法设计的要求：
  （1）正确性：所提出的算法能够正确解决问题
  （2）可读性：算法设计要便于理解
  （3）健壮性：当输入数据不合法时，要对异常进行适当处理
  （4）时间效率高和存储量低。

2. 算法的时间复杂度和空间复杂度

2.1 时间复杂度T(n)=O(f(n))

（1）基本概念
描述算法计算所需要时间的度量。其中n为问题的规模，f(n)为算法执行所有语句所需要的总的执行次数，n为问题的规模大小，f(n)为n的函数。
一般使用大O阶来体现算法的时间复杂度，也成为渐进时间复杂度。
为什么使用O(f(n))而不使用f(n)？
f(n)会随着问题规模n的变化而变化，当比较两个算法的时间复杂度性能好坏时，在不同的n下可能会得到不同的结果。因此只考虑f(n)随着n的变化趋势，从而确定算法的时间复杂度情况。
（2）常用的时间复杂度

常见的排序方法的时间复杂度比较：

2.2 算法的空间复杂度S(n)=O(f(n))

算法的空间复杂度通过计算算法所需要的存储空间来比较，记作S(n)=O(f(n))，f(n)为算法关于n所占存储空间的函数。