算法的复杂度（一）
术语“算法复杂性”用于衡量算法解决给定问题所需的步骤。它根据输入数据大小来评估算法执行的操作的计数顺序。
为了评估复杂性，始终考虑操作计数的顺序（近似值），而不是计算确切的步骤。
O（f）表示法表示算法的复杂性，也称为渐近表示法或Big O表示法。在此，f对应于其大小与输入数据相同的函数。渐进计算O（f）的复杂度决定了作为输入数据大小函数的算法所消耗的资源（例如CPU时间，内存等）的顺序。
复杂性可以以任何形式找到，例如常数，对数，线性，n * log（n），二次，三次，指数等。它只是常数，对数，线性等的阶数，完成特定算法所遇到的步骤。为了使其更加精确，我们经常将算法的复杂性称为“运行时间”。
算法的典型复杂性
-
恒定复杂度：
为O（1） 的复杂度。为了解决给定的问题，它需要执行恒定数量的步骤，例如1、5、10等。操作次数与输入数据大小无关。 -
对数复杂度：
为O（log（N）） 的复杂度。它执行log（N）步骤的顺序。为了对N个元素执行运算，通常将对数底为2。
对于N = 1,000,000，复杂度为O（log（N））的算法将经历20步（以恒定的精度）。在这里，对数基数对操作计数顺序没有必要的影响，因此通常将其省略。 -
线性复杂度：
- 它加强了O（N） 的复杂性。它包含与在N个元素上实现运算的元素总数相同的步骤数。
例如，如果存在500个元素，则大约需要500步。基本上，在线性复杂度中，元素的数量线性地取决于步骤的数量。例如，N个元素的步数可以是N / 2或3 * N。 - 它还加强了O（n * log（n）） 的运行时间。它对N个元素执行N * log（N）的顺序，以解决给定的问题。
对于给定的1000个元素，线性复杂度将执行10,000个步骤来解决给定的问题。
- 它加强了O（N） 的复杂性。它包含与在N个元素上实现运算的元素总数相同的步骤数。
-
二次幂复杂度： 施加O（n 2） 的复杂度。对于N个输入数据大小，它要对N个元素进行N 2个操作计数，才能解决给定的问题。
如果N = 100，它将可能为10,000步。换句话说，每当操作顺序趋于与输入数据大小呈二次关系时，就会导致二次复杂性。例如，对于N个元件，步骤被发现是在3 * N的顺序2 /2。 -
三次复杂度：施加O（n 3） 的复杂度。对于N个输入数据大小，它将对N个元素执行N 3步的顺序以解决给定的问题。
例如，如果存在100个元素，它将执行1,000,000个步骤。 -
指数复杂度： 施加O（2 n），O（N！），O（n k），… 的复杂度。对于N个元素，它将执行操作计数的顺序，该顺序取决于输入数据大小。
例如，如果N = 10，则指数函数2 N将得出1024。类似地，如果N = 20 ，则将得出1048 576，如果N = 100 ，则将得出具有30个数字的数字。指数函数N！增长更快；例如，如果N = 5将得到120。同样，如果N = 10将得到3,628,800，依此类推。
由于常量对操作计数的顺序影响不大，因此最好忽略它们。因此，要考虑算法是线性且等效效率高的算法，必须对相同数量的元素分别进行N，N / 2或3 * N次运算才能解决特定问题。
如何估算算法所花费的时间？
因此，要找出答案，我们将首先了解我们拥有的算法的类型。有两种算法：
- 迭代算法： 在迭代方法中，函数反复运行，直到满足条件或失败为止。它涉及循环构造。
- 递归算法： 在递归方法中，函数将自行调用，直到满足条件为止。它集成了分支结构。
但是，值得注意的是，以迭代方式编写的任何程序都可以编写为递归。同样，可以将递归程序转换为迭代程序，使这两种算法彼此等效。
但是要分析迭代程序，我们必须计算循环将要执行的次数，而在递归程序中，我们使用递归方程，即，我们根据F（n / 2）。
假设程序既不是迭代的也不是递归的。在那种情况下，可以得出结论，运行时间不依赖于输入数据大小，即无论输入大小如何，运行时间都将是恒定值。因此，对于此类程序，复杂度将为O（1）。
迭代程序
请考虑以下用简单的英语编写且与任何语法都不对应的程序。
示例1：
在第一个示例中，我们有一个整数i和一个从i等于1到n的for循环。现在出现了一个问题，名字被打印了多少次？
A()
{
int i;
for (i=1 to n)
printf("Trump");
}
由于i等于1到n，因此上面的程序将打印Trump数次。因此，复杂度将为O（n）。
示例2：
A()
{
int i, j:
for (i=1 to n)
for (j=1 to n)
printf("Trump");
}
在这种情况下，首先，外循环将运行n次，这样，每次内循环也将运行n次。因此，时间复杂度将为O（n 2）。
示例3：
A()
{
i = 1; S = 1;
while (S<=n)
{
i++;
S = S + i;
printf("Trump");
}
}
从上面的示例可以看出，我们有两个变量；i，S，然后有S <= n，这意味着S从1开始，并且每当S值达到S大于n的点时，整个循环就会停止。
在这里，i以1的步长递增，而S将以i的值递增，即i的递增是线性的。但是，S的增量取决于i。
最初;
i = 1，S = 1
第一次迭代后;
i = 2，S = 3
第二次迭代后;
i = 3，S = 6
第三次迭代后;
i = 4，S = 10…依此类推。
由于我们不知道n的值，因此我们假设它为k。现在，如果我们注意到上述情况下S的值正在增加；对于i = 1，S = 1; i = 2，S = 3；i = 3，S = 6；i = 4，S = 10；…
因此，它不过是前n个自然数之和的一系列，即到i达到k时，S的值为k（k + 1）/ 2。
要停止循环，
算法的复杂性
必须大于n，当我们求解此方程时，我们将得到
> n。因此，可以得出结论，我们得到的复杂度为O（√ ñ） 在这种情况下。
递归程序
考虑以下递归程序。
示例1：
A(n)
{
if (n>1)
return (A(n-1))
}
解决方案;
在这里，我们将看到简单的反向替换方法来解决上述问题。
T（n）= 1 + T（n-1） …等式 （1）
步骤1： 将n-1替换为等式n中的n。（1）
T（n-1）= 1 + T（n-2）...等式 （2）
步骤2： 将n-2替换为等式中n的位置。（1）
T（n-2）= 1 + T（n-3）…等式 （3）
步骤3： 代入方程式。（2）在等式中。（1）
T（n）= 1 + 1+ T（n-2）= 2 + T（n-2）…等式 （4）
步骤4： 代入eqn。（3）在等式中。（4）
T（n）= 2 +1 + T（n-3）= 3 + T（n-3）=…... = k + T（nk）…等式。（5）
现在，根据等式。（1），即T（n）= 1 + T（n-1），算法将一直运行到n> 1。基本上，n从一个很大的数字开始，然后逐渐减小。因此，当T（n）= 1时，算法最终停止，这种终止条件称为锚条件，基本条件或停止条件。
因此，对于k = n-1，T（n）将变为。
步骤5： 用eqn代替k = n-1。（5）
T（n）=（n-1）+ T（n-（n-1））=（n-1）+ T（1）= n-1 + 1
因此，T（n）= n或O（n）。
