算法复杂度简介

“您将如何计算算法的复杂度”这是面试中很常见的问题。您将如何比较两种算法?输入大小很大时,运行时间如何受到影响?因此,这是面试中经常问到的一些问题。在这篇文章中,我们将对算法的复杂性以及大符号进行基本介绍。

什么是算法?

算法是逐步解决特定问题的指令。
让我们举一个简单的例子。您想编写一种算法来收听特定的歌曲。
1)在计算机上搜索歌曲。
2)有歌曲吗?
            i。如果是,然后听那首歌。
           ii。如果否,请下载该歌曲,然后收听该歌曲。
因此,我们正在逐步解决问题。此逐步说明称为“算法”。

为什么需要评估算法?

您需要评估一种算法,以便找到用于解决给定问题并考虑各种因素和约束的最优化算法。
例如:
您想要从城市A到城市B,然后有多种选择,即乘飞机,公共汽车或火车。因此您需要根据预算和紧急程度在不同的选项中进行选择。

计数指令数:

对于不同的编程语言,指令的数量可以不同。
让s count number of 在 struction 对于 搜索ing a element 在 a 数组 .

让’假设我们的处理器为每个操作取一条指令:

  • 用于为变量分配值
  • 用于区分两个值
  • 乘或加
  • 退货声明

在最坏的情况下:

如果我们要搜索的元素是排序数组中的最后一个元素,那么这将是最坏的情况。
因此:

因此f(n)= 3n + 3

渐近行为:

在这里,我们将看到f(n)在n的值更大时的性能。
  • 随着n变大,我们可以忽略常数3,因为无论n的值如何,常数3始终为3。您可以将3视为初始化常数,并且不同的语言可能需要不同的时间进行初始化,因此其他函数仍为f(n)= 3n。
  • 我们可以忽略常数乘数,因为不同的编程语言可能会不同地编译代码。例如,阵列查找可以采用不同语言的不同数量的指令。所以剩下的是f(n)= n

您将如何比较算法?

您可以将算法的增长率与输入大小n进行比较
让s take a example.For solving same problem, you have two functions:
f(n)=4n^2 +2n+4 和f(n)=4n+4
对于f(n)=4n^22 +2n+4
所以在这里
f(1)= 4 + 2 + 4
f(2)= 16 + 4 + 4
f(3)= 36 + 6 + 4
f(4)= 64 + 8 + 4
….
如您所见,这里的贡献 n^22 随着n值的增加而增加。因此,对于非常大的n值,n的贡献 n^2 将是f(n)值的99%。因此在这里我们可以忽略低阶项,因为它们如上所述相对无关紧要。在此f(n)中,我们可以忽略2n和4.so
n^2+2n+4 ——–>n^2
对于f(n)=4n+4
所以在这里
f(1)= 4 + 4
f(2)= 8 + 4
f(3)= 12 + 4
f(4)= 16 + 4
….
如您所见,这里的贡献 n 随着n值的增加而增加。因此,对于非常大的n值,n的贡献 n 将是f(n)值的99%。因此在这里我们可以忽略低阶项,因为它们相对无关紧要。在这个f(n)中,我们可以忽略4和4作为常数乘数,如上所示,因此
4n+4 ——–>所以这里 n 是最高的增长率。
注意点:
我们放弃所有增长缓慢的术语,而保留增长最快的术语。

大O符号:

此表示法用于算法执行的理论量度。它给出了给定函数的严格上限。通常,它表示为f(n)= O(g(n)),其读数为“n的f是n的g的大o”.
正式定义:
f(n)= O(g(n))表示存在正常数c和n0,因此对于所有n≥n0,0≤f(n)≤cg(n)。 c和n0的值不能取决于n。
当您说O(g(n))时,这意味着它永远不会比g(n)更糟。话虽如此,这意味着O(g(n))的增长量与g(n)的增长量较小或相同。
因此O(n)包括O(n),O(logn)和O(1)。

因此,O(g(n))是显示算法复杂度的好方法。

让s take some example 和 calculate value 对于 c 和 n0.
1. f(n)= 4n + 3
以f(n)形式书写<= c * g(n),其中f(n)= 4n + 3和g(n)= 5n

4n + 3<对于n0 = 3和c = 5,= 5n。

或4n + 3<=6n 对于 n0=2 和 c=6
以f(n)形式书写<= c * g(n),其中f(n)= 4n + 3和g(n)= 6n
因此对于n0和c可以有多个值,其中f(n)<= c g(n)将得到满足。

2. f(n)=4n^2+2n+4
以f(n)形式书写<=c*g(n) with f(n)=4n^2 +2n+4 和g(n)= 5n ^ 2
4n^2 +2n+4<=5n^2 对于n0 = 4和c = 5

计算算法复杂度的经验法则:

可以使用计数循环次数或迭代次数来分析简单程序。

连续声明:
我们需要增加连续语句的时间复杂度。

f(n)= c1 + c2;
所以O(f(n))= 1

计算一个简单循环的复杂度:

循环的时间复杂度可以通过循环内语句的运行时间乘以迭代总数来确定。

f(n)= c2 * n + c1;
所以O(n)= n

 
计算嵌套循环的复杂度:

它是每个循环的迭代结果。

f(n)= c2 * n * n + c1
所以O(f(n))= n^2

 
如果和其他:

当您具有if和else语句时,将使用两者中较大的一个来计算时间复杂度。

f(n)= c1 + c2 + c3 +(c4 + c5 + c6)* n
所以o(f(n))= n

对数复杂度

让我们借助示例来了解对数复杂度。您可能知道二进制搜索。当您想在排序数组中查找值时,我们使用二进制搜索。

现在让’s假设我们的数组是:

我们想在上面的数组中搜索74。下图将说明二进制搜索将如何在这里工作。

当您仔细观察时,在每次迭代中,您都将数组范围缩小了一半。在每次迭代中,我们都根据soretedArray [mid]覆盖first或last的值。
因此对于
第0次迭代:n
第一次迭代:n / 2
第二次迭代n / 4
第三次迭代n / 8。
概括以上等式:
对于第i次迭代:n /2i

因此,当我们剩下1个元素(即任何i)时,迭代将结束,这将是我们的最后一次迭代:
1=n/2i;
2i = n;
记录后
i = log(n);
因此得出结论,执行二进制搜索所需的迭代次数为log(n),因此 二进制搜索的复杂度为log(n)
就像在我们的示例中一样,我们有n为8。进行了3次迭代(8->4->2->1) 和 3 is log(8).
因此,如果我们在每次迭代中将输入大小除以k,则其复杂度将为O(logk(n)),即log(n)为基础k。

让s take an example:

上面代码的复杂度为O(log(n))。

行使:

让s do some exercise 和 find complexity of given code:

1.

答:

复杂度将为O(n)

2.

答:

复杂度将为:n + n * n—>O(n^2)

3.

答:

复杂度将为n * n / 2 * log(n)–> n^2日志(n)

 4.

答:

复杂度将为n / 2 * n / 2 * n–> n^3

相关文章

Comments

发表评论

您的电子邮件地址不会被公开。 必需的地方已做标记 *

订阅我们的新闻

获取质量教程到您的收件箱。现在订阅。