通过简单的例子理解时间复杂性-yiteyi-C++库

很多学生在理解时间复杂性的概念时会感到困惑，但在本文中，我们将用一个非常简单的例子来解释它：想象一下，在一个有100名学生的教室里，你把钢笔给了一个人。现在，你想要那支笔。这里有一些方法可以找到钢笔和O顺序。 O（n） ^2. ): 你去问问班上的第一个人，他有没有钢笔。另外，你问这个人教室里其他99个人是否有那支笔等等，这就是我们所说的O（n） ^2. ). O（n）： 单独去问每个学生是O（N）。 O（logn）： 现在我把全班分成两组，然后问：“是在教室的左侧，还是右侧？”然后我把这群人分成两部分，再问一遍，以此类推。重复这个过程，直到你剩下一个拿着你的笔的学生。这就是你所说的O（logn）的意思。我可能需要做O（n ^2. )如果只有一个学生知道笔隐藏在哪个学生身上，则进行搜索。如果一个学生有钢笔，只有他们知道，我会用O（n）。如果所有学生都知道，我会使用O（logn）搜索，但只有在我猜对的时候才会告诉我。

null

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

另一个例子： 算法/代码的时间复杂度为不等于执行特定代码所需的实际时间，但等于语句执行的次数。我们可以用时间命令来证明这一点。例如，用C/C++或任何其他语言编写代码，以在N个数字之间找到最大值，其中N从10、100、1000、10000变化。并使用以下命令在基于Linux的操作系统（Fedora或Ubuntu）上编译代码：

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

你会得到令人惊讶的结果，即对于N=10，你可能会得到0.5ms的时间，对于N=10000，你可能会得到0.2ms的时间。此外，您将在不同的机器上获得不同的计时。因此，我们可以说，执行代码所需的实际时间取决于机器（无论您使用的是奔腾1还是奔腾5），如果您的机器位于LAN/WAN中，它还考虑了网络负载。即使在同一台机器上，您也无法为相同的代码获得相同的计时，这就是当前网络负载增加的原因。现在，问题出现了，如果时间复杂度不是执行代码所需的实际时间，那么它是什么？

答案是： 我们不考虑执行代码中每个语句所需的实际时间，而是考虑每个语句执行多少次。例如：

C

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

输出

Hello World

在上面的代码“你好，世界！！！”在屏幕上只打印一次。因此，时间复杂度是恒定的：O（1），即无论您使用的是哪种操作系统或哪种机器配置，执行代码所需的时间量都是恒定的。

现在考虑另一个代码：

C

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

JAVA

                         class                                     GFG {                       
           
                                                 public                                     static                                     void                                     main(String []args) {                       
                                                 int                                     i, n =                                     8                                     ;                       
                                                 for                                     (i =                                     1                                     ; i <= n; i++) {                       
                                                 System.out.printf(                                     "Hello Word !!!"                                     );                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Rajput-Ji                       

输出

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

在上面的代码“你好，世界！！！”将打印N次。所以，上述代码的时间复杂度为O（N）。资料来源： Reddit

其他信息： 例如：让我们考虑一种具有下列规格的模型机： –单处理器 –32位 –顺序执行 –1个单位的算术和逻辑运算时间 –分配和返回报表的单位时间

1.两个数字之和：

C

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.列表中所有元素的总和：

C

                         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+4=C1*n+C2=O（n）

3.矩阵所有元素之和：

对于这个问题，复杂性是一个多项式方程（平方矩阵的二次方程） 矩阵nxn=>Tsum=an ^2. +bn+c 对于这个Tsum，如果按n的顺序 ^2. =O（n） ^2. ) 以上代码不在IDE中运行，因为它们是伪代码，与任何编程语言都不相似。 因此，从上面我们可以得出结论，执行时间随着我们使用输入进行的操作类型的增加而增加。上面的O->被称为Big–Oh，这是一种渐近符号。还有其他渐近符号，如θ和欧姆。

如何比较算法？

为了比较算法，让我们定义几个客观指标：

执行时间： 这不是一个很好的衡量标准，因为执行时间是特定于特定计算机的。
执行了许多语句： 这不是一个很好的衡量标准，因为语句的数量随着编程语言以及单个程序员的风格而变化。
理想解决方案： 假设我们将给定算法的运行时间表示为输入大小n（即f（n））的函数，并比较与运行时间对应的这些不同函数。这种比较与机器时间、编程风格等无关。

你可以参考： 了解渐近符号 本文作者提供的其他信息如下： 帕桑格·巴拉吉·拉奥。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章