Yas*_*ser 845 algorithm complexity-theory time-complexity
问题
如何找到算法的时间复杂度？
在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次
i ++; 这将被执行N次
所以这个循环所需的操作数量是
{1+(N + 1)+ N} = 2N + 2
注意:这仍然可能是错误的,因为我对计算时间复杂度的理解没有信心
我想知道什么？
好吧,所以这些小基本计算我想我知道,但在大多数情况下,我已经看到了时间复杂度
O(N),O(N2),O(log n)的,为O(n!) ......和许多其他,
任何人都可以帮我理解如何计算算法的时间复杂度？我相信有很多像我这样的新手想知道这一点.
Ach*_*how 375
这是一篇很好的文章: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个循环(迭代或递归)组成,因此算法是线性和对数的组合.
一般来说,对一个维度中的每个项目执行某些操作是线性的,对二维中的每个项目执行某些操作是二次的,将工作区域分成两半是对数的.还有其他Big O指标,如立方,指数和平方根,但它们并不常见.Big O表示法被描述为O(),其中是度量.快速排序算法将被描述为O(N*log(N)).
请注意,这些都没有考虑最佳,平均和最差情况的措施.每个都有自己的Big O表示法.另请注意,这是一个非常简单的解释.Big O是最常见的,但它也显示得更复杂.还有其他符号,如大欧米茄,小o和大theta.您可能不会在算法分析课程之外遇到它们.;)
And*_*zos 371
如何找到算法的时间复杂度
您可以根据输入的大小计算它将执行多少个机器指令,然后将表达式简化为最大(当N非常大)时,可以包含任何简化的常量因子.
例如,让我们看看我们如何简化2N + 2机器指令来描述它O(N).
我们为什么要删除这两个2？
当N变大时,我们对算法的性能感兴趣.
考虑两个术语2N和2.
当N变大时,这两个术语的相对影响是什么？假设N是一百万.
然后第一个词是200万,第二个词只有2.
出于这个原因,我们放弃了大N的最大条件.
所以,现在我们已经离开2N + 2了2N.
传统上,我们只对恒定因素的表现感兴趣.
这意味着当N很大时,我们并不在乎是否存在性能差异的恒定倍数.无论如何,2N的单位首先没有明确定义.因此,我们可以乘以或除以常数因子来得到最简单的表达式.
所以2N变得公正N.
Yas*_*ser 156
摘自此处 - 算法时间复杂度简介
在计算机科学中,算法的时间复杂度量化算法作为表示输入的字符串长度的函数运行所花费的时间量.
算法的时间复杂度通常使用大O表示法表示,其不包括系数和低阶项.当以这种方式表达时,时间复杂度被称为渐近地描述,即,随着输入大小变为无穷大.
例如,如果算法对大小为n的所有输入所需的时间最多为5n 3 + 3n,则渐近时间复杂度为O(n 3).稍后会详细介绍.
几个例子:
如果算法需要相同的时间量而不管输入大小如何,则称算法在恒定时间内运行.
例子:
如果算法的时间执行与输入大小成正比,则称算法以线性时间运行,即随着输入大小的增加,时间线性增长.
考虑下面的例子,下面我是线性搜索一个元素,它的时间复杂度为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;
}
}
更多例子:
如果算法的时间执行与输入大小的对数成比例,则称算法以对数时间运行.
示例:二进制搜索
回想一下"二十个问题"游戏 - 任务是猜测一个区间中隐藏数字的值.每当你猜测时,你会被告知你的猜测是太高还是太低.二十个问题游戏意味着使用您的猜测数量将间隔大小减半的策略.这是称为二分搜索的一般问题解决方法的示例
如果算法的时间执行与输入大小的平方成比例,则称算法以二次时间运行.
例子:
zan*_*ngw 95
虽然这个问题有一些很好的答案.我想在这里给出另一个答案,其中有几个例子loop.
O(n):时间如果循环变量递增/递减恒定量,则循环的复杂度被认为是O(n).例如,以下函数具有O(n)时间复杂度.
// Here c is a positive integer constant
for (int i = 1; i <= n; i += c) {
// some O(1) expressions
}
for (int i = n; i > 0; i -= c) {
// some O(1) expressions
}
O(n ^ c):嵌套循环的时间复杂度等于执行最内层语句的次数.例如,以下样本循环具有O(n ^ 2)时间复杂度
for (int i = 1; i <=n; i += c) {
for (int j = 1; j <=n; j += c) {
// some O(1) expressions
}
}
for (int i = n; i > 0; i += c) {
for (int j = i+1; j <=n; j += c) {
// some O(1) expressions
}
例如,Selection sort和Insertion Sort具有O(n ^ 2)时间复杂度.
O(Logn)时间如果将循环变量除以/乘以常量,则循环的复杂度被视为O(Logn).
for (int i = 1; i <=n; i *= c) {
// some O(1) expressions
}
for (int i = n; i > 0; i /= c) {
// some O(1) expressions
}
例如,二进制搜索具有O(Logn)时间复杂度.
O(LogLogn)时间如果循环变量以指数方式减少/增加一个恒定量,则循环的复杂度被视为O(LogLogn).
// Here c is a constant greater than 1
for (int i = 2; i <=n; i = pow(i, c)) {
// some O(1) expressions
}
//Here fun is sqrt or cuberoot or any other constant root
for (int i = n; i > 0; i = fun(i)) {
// some O(1) expressions
}
时间复杂度分析的一个例子
int fun(int n)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < n; j += i)
{
// Some O(1) task
}
}
}
分析:
For i = 1, the inner loop is executed n times.
For i = 2, the inner loop is executed approximately n/2 times.
For i = 3, the inner loop is executed approximately n/3 times.
For i = 4, the inner loop is executed approximately n/4 times.
…………………………………………………….
For i = n, the inner loop is executed approximately n/n times.
因此,上述算法的总时间复杂度(n + n/2 + n/3 + … + n/n)变为n * (1/1 + 1/2 + 1/3 + … + 1/n)
关于系列的重要事项(1/1 + 1/2 + 1/3 + … + 1/n)等于O(Logn).所以上面代码的时间复杂度是O(nLogn).
Yas*_*ser 72
1 - 基本操作(算术,比较,访问数组的元素,赋值):运行时间总是不变的O(1)
示例:
read(x) // O(1)
a = 10; // O(1)
a = 1.000.000.000.000.000.000 // O(1)
2 - 如果then else语句:仅从两个或多个可能的语句中获取最大运行时间.
例:
age = read(x) // (1+1) = 2
if age < 17 then begin // 1
status = "Not allowed!"; // 1
end else begin
status = "Welcome! Please come in"; // 1
visitors = visitors + 1; // 1+1 = 2
end;
因此,上述伪代码的复杂度是T(n)= 2 + 1 + max(1,1 + 2)= 6.因此,它的大哦仍然是常数T(n)= O(1).
3 - 循环(for,while,repeat):此语句的运行时间是循环次数乘以循环内的操作数.
例:
total = 0; // 1
for i = 1 to n do begin // (1+1)*n = 2n
total = total + i; // (1+1)*n = 2n
end;
writeln(total); // 1
因此,其复杂度为T(n)= 1 + 4n + 1 = 4n + 2.因此,T(n)= O(n).
4 - 嵌套循环(循环内部循环):由于主循环内至少有一个循环,因此该语句的运行时间使用O(n ^ 2)或O(n ^ 3).
例:
for i = 1 to n do begin // (1+1)*n = 2n
for j = 1 to n do begin // (1+1)n*n = 2n^2
x = x + 1; // (1+1)n*n = 2n^2
print(x); // (n*n) = n^2
end;
end;
分析算法时有一些常见的运行时间:
O(1) - 恒定时间恒定时间表示运行时间是恒定的,它不受输入大小的影响.
O(n) - 线性时间当算法接受n个输入大小时,它也会执行n个操作.
O(log n) - 具有运行时间O(log n)的对数时间算法比O(n)略快.通常,算法将问题划分为具有相同大小的子问题.示例:二进制搜索算法,二进制转换算法.
O(n log n) - 线性时间此运行时间通常出现在"分而治之算法"中,它将问题递归地分解为子问题,然后在n时间内合并它们.示例:合并排序算法.
O(n 2) - 二次时间看气泡排序算法!
O(n 3) - 立方时间它与O(n 2)具有相同的原理.
O(2 n) - 指数时间当输入变大时非常慢,如果n = 1000.000,T(n)将是21000.000.Brute Force算法具有此运行时间.
O(n!) - 阶乘时间最慢!!! 示例:旅行商问题(TSP)
摘自这篇文章.很好解释应该给读一个.
Ale*_*gić 41
当你分析代码时,你必须逐行分析它,计算每个操作/识别时间复杂度,最后,你必须总结它以获得全局.
例如,您可以使用一个具有线性复杂度的简单循环,但稍后在同一个程序中,您可以使用具有立方复杂度的三重循环,因此您的程序将具有立方复杂性.增长的功能顺序就在这里发挥作用.
让我们看一下算法时间复杂度的可能性,你可以看到我上面提到的增长顺序:
恒定时间有增长的顺序1,例如:a = b + c.
对数时间有一个增长的顺序LogN,它通常发生在你将某事分成两半(二分搜索,树,甚至循环)或以相同方式乘以某些东西时.
N例如,线性的增长顺序
int p = 0;
for (int i = 1; i < N; i++)
p = p + 2;
线性,增长的顺序n*logN通常发生在分而治之的算法中.
立方,增长的顺序N^3,经典的例子是一个三重循环,你检查所有三胞胎:
int x = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < N; k++)
x = x + 2
指数,增长顺序2^N通常在您进行穷举搜索时发生,例如检查某些集的子集.
Ric*_*ard 33
简而言之,时间复杂度是一种总结算法的操作数或运行时如何随输入大小增加而增长的方式.
像生活中的大多数事情一样,鸡尾酒会可以帮助我们理解.
上)
当你到达聚会时,你必须握住每个人的手(对每个项目进行操作).随着与会者人数的N增加,你需要时间/工作来撼动每个人的手O(N).
为什么O(N)不cN呢？
与人握手所需的时间有所不同.您可以将其平均并以常量捕获它c.但基本操作在这里---握手和大家---将永远是成正比的O(N),不管是什么c了.在辩论我们是否应该参加鸡尾酒会时,我们常常更感兴趣的是,我们必须会见每个人,而不是那些会议的细节.
O(N ^ 2)
鸡尾酒会的主持人希望你玩一个愚蠢的游戏,每个人都遇到其他人.因此,你必须遇见N-1其他人,因为下一个人已经遇到你,他们必须遇见N-2别人,等等.这个系列的总和是x^2/2+x/2.随着与会者人数的增加,这个x^2词变得越来越快,所以我们放弃其他所有内容.
O(N ^ 3)
您必须与其他所有人见面,并且在每次会议期间,您必须谈论会议室中的其他人.
O(1)
主持人想宣布一些事情.他们敲着酒杯,大声说话.每个人都听到了他们.事实证明,无论有多少与会者,此操作总是花费相同的时间.
O(log N)
主持人按字母顺序排列在桌旁.丹在哪里？你的理由是他必须介于亚当和曼迪之间(当然不是曼迪和扎克之间!).鉴于此,他是乔治和曼迪之间吗？不,他必须介于亚当和弗雷德之间,以及辛迪和弗雷德之间.等等...我们可以通过查看该组的一半然后是该组的一半来有效地定位Dan.最后,我们看看O(log_2 N)个体.
O(N log N)
你可以使用上面的算法找到坐在桌子旁的地方.如果有很多人一次一个地来到桌子上,并且所有人都这样做了,那将花费O(N log N)时间.事实证明,必须比较任何项目集合所需的时间.
最好/最坏情况
你到达派对并需要找到Inigo - 需要多长时间？这取决于你什么时候到达.如果每个人都在四处奔波你就会遇到最糟糕的情况:这需要O(N)时间.但是,如果每个人都坐在桌旁,那只需要O(log N)时间.或者也许你可以利用主持人的酒杯大喊大叫,只需要O(1)时间.
假设主机不可用,我们可以说Inigo查找算法具有下限O(log N)和上限O(N),具体取决于您到达时的方状态.
空间与传播
同样的想法可以应用于理解算法如何使用空间或通信.
Knuth写了一篇关于前者的好文章,名为"歌曲的复杂性".
定理2:存在任意长的复杂度为O(1)的歌曲.
证明:(由于凯西和阳光乐队).考虑由(15)定义的歌曲Sk,但是
V_k = 'That's the way,' U 'I like it, ' U
U = 'uh huh,' 'uh huh'
对于所有k.