代码的时间复杂度？！ [英] time complexity of the code?!

问题描述

这些算法的最佳情况和最坏情况分析的时间复杂度O（n）是多少？



int n = int.parse（console.readline） （））;

int i = n;

while（i> 1）

{

console。写（i）;

i％= 2;

}

______________________________________



int n = int.parse（console.readline（））;

int x = 0;

for（int i = 0; i< = n; ++ i）

{

for（int j = 0; j< = i; ++ j）

{

for（k = 1; k <= n; k ++）

{

x ++;

}

}

}



是第一个O（n）和第二个O（n ^ 3）？我对吗？它是如何工作的？

what is the time complexity O(n) of these algorithm for the best case and worst case analysis?

int n = int.parse(console.readline());
int i=n;
while(i>1)
{
console.write(i);
i%=2;
}
______________________________________

int n = int.parse(console.readline());
int x=0;
for(int i=0;i<=n;++i)
{
for(int j=0;j<=i;++j)
{
for(k=1;k<=n;k++)
{
x++;
}
}
}

is the first one O(n) and second one O(n^3)? am i right? how that works?

推荐答案

由于两个算法都是线性的 - 它们对于给定值n总是花费相同的时间 - 它们是根据定义总是O（n）

所以最好和最坏的情况分析是微不足道的：它们都是相同的。



忽略这一点，我正在说出我的背后。我责备缺少咖啡因...：O



这些都不是O（n）：而n的值将对其产生重大影响执行它们所花费的时间。

仔细查看代码：第一个示例循环0到10之间的n值是多少次？

Since both "algorithms" are linear - they always take the same amount of time for a given value "n" - they are by definition always O(n)
So the best and worst case analysis is trivial: they are both the same.

Ignore that, I'm talking out my backside. I blame an absence of caffeine... :O

Neither of those is O(n) at all: and the value of n will have a big impact on the time taken to execute them.
Look at the code more carefully: how many times does the first example loop for the values of n between 0 and 10?

这篇关于代码的时间复杂度？！的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！