算法和复杂性

2024-05-16 12:06:07 441

算法

算法是一组有限的指令，如果遵循这些指令，它们就可以完成特定的任务。它不是特定于语言的，我们可以使用任何语言和符号来表示指令。

输入：零个或多个输入从外部提供给算法。

输出：一种算法至少产生一个输出。

明确性：每条指令都清晰明确。

有限性： 在算法中，针对所有不同情况，将在有限数量的步骤后终止该算法。

有效性：每条指令必须非常基础，因此这些指令的目的必须非常明确。

算法分析是计算复杂性的重要组成部分。复杂性理论为算法解决任何计算任务所需的资源提供了理论估计。算法分析是根据所需的时间和大小（实现时用于存储的内存大小）分析算法解决问题的能力的过程。但是，算法分析的主要问题是所需的时间或性能。

算法的复杂度计算了算法对于大小(n)的输入所需的时间和空间量。算法的复杂度可以分为两种类型。的时间复杂度和空间复杂度。

时间复杂度定义为确定执行该算法所需的总时间的公式的过程。该计算完全独立于实现和编程语言。

空间复杂度定义为定义公式的过程，该公式用于预测成功执行算法需要多少存储空间。通常将存储空间视为主内存。