如何找到算法的时间复杂度
问题
如何找到算法的时间复杂度?
在SO上发布问题之前我做了什么?
我已经通过这个,这个和其他许多链接
但是,没有我能够找到如何计算时间复杂度的清晰直接的解释。
我知道什么 ?
说一个简单的代码如下:
char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time
说一个像下面这样的循环:
for (int i = 0; i < N; i++) {
Console.Write('Hello World !');
}
int i = 0; 这将只执行一次 。 时间实际上是计算为i=0
而不是声明。
我<N; 这将被执行N + 1次
我++; 这将被执行N次
所以这个循环所需的操作数量是
{1+(N + 1)+ N} = 2N + 2
注意:这仍然可能是错误的,因为我对计算时间复杂度的理解没有把握
我想知道什么?
好吧,我想我知道这些小的基本计算,但在大多数情况下,我已经看到了时间复杂度
O(N),O(n2),O(log n),O(n!) ....等等,
任何人都可以帮助我理解如何计算算法的时间复杂度? 我确信有很多像我这样想知道的新手。
如何找到算法的时间复杂度
您将根据其输入大小加上要执行的机器指令数量,然后将表达式简化为最大(当N非常大时)项,并且可以包含任何简化常数因子。
例如,让我们看看我们如何简化2N + 2
机器指令来描述这只是O(N)
。
为什么我们删除两个2
秒?
随着N变大,我们对算法的性能感兴趣。
考虑两个术语2N和2。
当N变大时,这两个术语的相对影响是什么? 假设N是一百万。
那么第一个学期是200万,第二个学期只有2个。
出于这个原因,我们放弃了大N的所有条款。
所以,现在我们已经从2N + 2
变成了2N
。
传统上,我们只对性能持续不变的因素感兴趣。
这意味着当N很大时,我们并不在乎是否存在性能差异的倍数倍数。 无论如何,2N的单位并没有明确的定义。 因此,我们可以乘以或除以一个常数因子以得到最简单的表达式。
所以2N
变成了N
这是一篇优秀的文章:http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm
下面的答案是从上面复制(如果优秀的链接崩溃)
计算时间复杂度的最常用指标是Big O符号。 这消除了所有常数因素,因此当N接近无穷大时,可以根据N估计运行时间。 一般来说,你可以这样想:
statement;
是恒定的。 声明的运行时间不会因N而改变。
for ( i = 0; i < N; i++ )
statement;
是线性的。 循环的运行时间与N成正比。当N加倍时,运行时间也是。
for ( i = 0; i < N; i++ ) {
for ( j = 0; j < N; j++ )
statement;
}
是二次的。 两个循环的运行时间与N的平方成正比。当N加倍时,运行时间增加N * N。
while ( low <= high ) {
mid = ( low + high ) / 2;
if ( target < list[mid] )
high = mid - 1;
else if ( target > list[mid] )
low = mid + 1;
else break;
}
是对数的。 算法的运行时间与N可以除以2的次数成正比。这是因为该算法在每次迭代时将工作区域分成两半。
void quicksort ( int list[], int left, int right )
{
int pivot = partition ( list, left, right );
quicksort ( list, left, pivot - 1 );
quicksort ( list, pivot + 1, right );
}
是N * log(N)。 运行时间由对数的N个循环(迭代或递归)组成,因此该算法是线性和对数的组合。
一般来说,在一个维度上对每个项目做一些事情是线性的,对于每个维度来说,二维维度中的每个项目都是二次的,而将工作区域分成两半是对数的。 还有其他的大O措施,如立方体,指数和平方根,但它们几乎不常见。 大O符号被描述为O()其中是度量。 快排算法将被描述为O(N * log(N))。
请注意,这些都没有考虑到最佳,平均和最差情况下的措施。 每个人都有自己的Big O符号。 还要注意这是一个非常简单的解释。 大O是最常见的,但它也更复杂。 还有其他符号,如大欧米茄,小o和大θ。 在算法分析课程之外,你可能不会遇到它们。 ;)
从这里开始 - 介绍算法的时间复杂度
1.介绍
在计算机科学中,算法的时间复杂度量化算法作为代表输入的字符串长度的函数运行所花费的时间量。
2.大O符号
算法的时间复杂度通常用大O符号来表示,它不包括系数和低阶项。 当以这种方式表达时,据说时间复杂度渐近地被描述,即,随着输入大小变为无穷大。
例如,如果算法在所有n的输入上所需的时间至多为5n3 + 3n,则渐近时间复杂度为O(n3)。 稍后更多。
几个例子:
3. O(1)恒定时间:
如果算法需要相同的时间量,而不管输入大小如何,算法被认为在恒定时间内运行。
例子:
4. O(n)线性时间
如果算法的时间执行与输入大小成正比,即随着输入大小增加,时间线性增长,则算法被称为以线性时间运行。
考虑下面的例子,下面我线性搜索一个元素,这有一个时间复杂度为O(n)。
int find = 66;
var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 };
for (int i = 0; i < numbers.Length - 1; i++)
{
if(find == numbers[i])
{
return;
}
}
更多示例:
5. O(log n)对数时间:
如果算法的时间执行与输入大小的对数成比例,则算法被称为在对数时间运行。
示例:二进制搜索
回想一下“二十问题”游戏 - 任务是在一个区间内猜测隐藏号码的值。 每次你猜测,你都会被告知你的猜测是太高还是太低。 二十个问题游戏意味着使用您的猜测数量减半区间大小的策略。 这是一种称为二进制搜索的一般问题解决方法的例子
6. O(n2)二次时间
如果算法的时间执行与输入大小的平方成正比,则算法被称为以二次方式运行。
例子:
7.一些有用的链接
上一篇: How to find time complexity of an algorithm
下一篇: O for PHP functions