通过简单的示例了解时间复杂性（通俗理解） _数据结构

很多学生在理解时间复杂度的概念时会感到困惑, 但是在本文中, 我们将用一个非常简单的示例来解释它：
【通过简单的示例了解时间复杂性（通俗理解）】想象一下一个有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=1no of times=1 for i=0 to n-1//cost=2no of times=n+1 (+1 for the end false condition) sum = sum + A[i]//cost=2no of times=n return sum//cost=1no 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。