通过简单的示例了解时间复杂性（通俗理解）

很多学生在理解时间复杂度的概念时会感到困惑, 但是在本文中, 我们将用一个非常简单的示例来解释它：

想象一下一个有100个学生的教室, 你在其中将笔交给一个人。现在, 你想要那支笔。以下是一些查找笔的方法以及O阶数是什么。

O(n^2)：你去问问班上的第一人, 如果他有钢笔。另外, 你问这个人关于教室中其他99个人是否有笔等,

这就是我们所说的O(n^2)。

O(n)：去问每个学生分别是O(N)。

O(log n)：现在, 我将课堂分为两组, 然后问："是在教室的左侧还是右侧？"然后, 我将那个小组分成两部分, 然后再次询问, 依此类推。重复此过程, 直到剩下一名拥有笔的学生。这就是O(log n)的意思。

我可能需要做O(n2)搜索是否只有一位学生知道笔藏在哪位学生身上。如果一个学生拿着笔, 只有他们知道, 我会使用O(n)。如果所有学生都知道, 我会使用O(log n)搜索, 但是只会告诉我是否猜对了。

注意 ：

我们对程序执行过程中输入的时间的增长率感兴趣。

另一个例子

算法/代码的时间复杂度为不等于执行特定代码所需的实际时间, 但等于语句执行的次数。我们可以通过使用time命令来证明这一点。例如, 用C++/ C++或任何其他语言编写代码以查找N个数字之间的最大值, 其中N的范围为10、100、1000、10000。然后使用以下命令在基于Linux的操作系统(Fedora或Ubuntu)上编译该代码：

gcc program.c – o program
run it with time ./program

你会得到令人惊讶的结果, 即对于N = 10你可能会获得0.5毫秒的时间, 对于N = 10, 000你可能会获得0.2毫秒的时间。另外, 你将在不同的计算机上获得不同的时间。因此, 可以说执行代码所需的实际时间取决于计算机(无论你使用的是pentium1还是pentiun5), 并且如果你的计算机位于LAN/WAN中, 它还会考虑网络负载。即使你在同一台机器上使用相同的代码也不会获得相同的时间, 这是当前网络负载的原因。

现在, 如果时间复杂度不是实际时间要求执行代码, 那么就会出现问题, 那是什么？

答案是 ：

我们不考虑执行代码中每个语句所需的实际时间, 而是考虑每个语句执行多少次。

例如：

#include <stdio.h>
int main()
{
     printf ( "Hello World" );
}

输出如下：

Hello World

在上面的代码" Hello World !!!"中在屏幕上仅打印一次。因此, 时间复杂度是恒定的：O(1), 即每次使用恒定时间执行代码, 无论你使用的是哪种操作系统或机器配置。

现在考虑另一个代码：

#include <stdio.h>
void main()
{
     int i, n = 8;
     for (i = 1; i <= n; i++) {
         printf ( "Hello Word !!!" );
     }
}

输出如下：

Hello Word !!!Hello Word !!!Hello Word !!!Hello Word !!!
Hello Word !!!Hello Word !!!Hello Word !!!Hello Word !!!

在上面的代码" Hello World !!!"中将打印N次。因此, 以上代码的时间复杂度为O(N)。

资源 ：Reddit

附加信息 ：

例如：

让我们考虑具有以下规格的模型机：

–单处理器

–32位

–顺序执行

–1单位时间的算术和逻辑运算

–1单位时间用于赋值和返回语句

1. 2个数字之和：

Pseudocode:
Sum(a, b){
return a+b  //Takes 2 unit of time(constant) one for arithmetic operation and one for return.(as per above conventions)   cost=2 no of times=1
}

Tsum = 2 = C++= O(1)

2.列表中所有元素的总和：

Pseudocode:
list_Sum(A, n){ //A->array and n->number of elements in the array
total =0           //cost=1  no of times=1
for i=0 to n-1     //cost=2  no of times=n+1 (+1 for the end false condition)
sum = sum + A[i]   //cost=2  no of times=n 
return sum         //cost=1  no of times=1
}

Tsum = 1 + 2 *(n + 1)+ 2 * n + 1 = 4n +1 = C1 * n + C2 = O(n)

3.矩阵所有元素的总和：

对于这一点, 复杂度是一个多项式方程(方矩阵的二次方程)

矩阵nxn => Tsum = an^2+ bn + c

对于这个Tsum, 如果为 n^2 = O(n^2)

上面的代码不是伪代码, 并且不类似于任何编程语言, 因此无法在IDE中运行。

因此, 从以上我们可以得出结论, 执行时间随着使用输入进行的操作类型的增加而增加。

上面的O->被称为Big –哦, 这是一个渐近符号。还有其他渐近符号, 例如theta和Ohm。

你可以参考：了解渐近符号

本文作者提供的其他信息是Pathange Balaji Rao。

---