英文:
Why do if-elses, which are said to have no effect when calculating time complexity, create a time difference?
问题
当我测试下面的代码的运行速度时,在最坏的情况下需要26秒,在最好的情况下需要1秒。但是,根据大O符号表示法:它是O(1)和O(1)——常数复杂度。无论数据集有多大,常数复杂度的情况下,运行时间和资源使用始终保持恒定。
static void Main(string[] args)
{
Console.WriteLine(DateTime.Now);
for (int i = 0; i < 1000000; i++)
{
string x = "aafdsggfjjrffdfhgfhgjfdgfdgfr";
string y = string.Empty;
if (x.Contains("rghfjgkhhj"))
{
y = "fdsfdsfds";
}
else if (x.Contains("rghfjgkhhj"))
{
y = "fdsfdsfds";
}
else if (x.Contains("rghfjgkhhj"))
{
y = "fdsfdsfds";
}
else if (x.Contains("rghfjgkhhj"))
{
y = "fdsfdsfds";
}
.
.
.
.
.
500次
else if (x.Contains("rghfjgkhhj"))
{
y = "fdsfdsfds";
}
}
Console.WriteLine(DateTime.Now);
Console.ReadLine();
}
所以,既然它是O(1),为什么会有26秒的差异呢?(如果你不知道如何计算时间复杂度,请不要评论。)
英文:
When I test the running speed of the code below, it takes 26 seconds in the worst-case and takes 1 second in the best-case. But ,according to Big-O notation: it's a O(1) and
** O(1)— Constant Complexity**
No matter how large the dataset you have in Constant complexity, the time to run and the resource used are always constant.
static void Main(string[] args)
{
Console.WriteLine(DateTime.Now);
for (int i = 0; i < 1000000; i++)
{
string x = "aafdsggfjjrffdfhgfhgjfdgfdgfr";
string y = string.Empty;
if (x.Contains("rghfjgkhhj"))
{
y = "fdsfdsfds";
}
else if (x.Contains("rghfjgkhhj"))
{
y = "fdsfdsfds";
}
else if (x.Contains("rghfjgkhhj"))
{
y = "fdsfdsfds";
}
else if (x.Contains("rghfjgkhhj"))
{
y = "fdsfdsfds";
}
.
.
.
.
.
500 times
else if (x.Contains("rghfjgkhhj"))
{
y = "fdsfdsfds";
}
}
Console.WriteLine(DateTime.Now);
Console.ReadLine();
}
So , since it is o(1) there is no time difference then why 26 seconds difference?
(Please don't comment if you don't know how to calculate time complexity.
)
答案1
得分: 1
根据用户某位程序员的评论,时间复杂度就像它听起来的那样抽象 - 它不告诉您代码将在多少秒(或任何时间单位)内完成运行,而是为代码根据其输入的规模提供了一个抽象评估,用来衡量其处理输入的好坏程度。
更不用说实际运行时间还受到其他因素的影响,例如:
- 内存分配速度
- CPU的时钟频率
等等。
规模可以是您的方法基于的任何东西:数组的长度、字符串的长度、要处理的字节数等等。
在这种情况下,您通过for
循环中的迭代次数来衡量您的O
:
在这里,一切都是恒定的:
for循环
的迭代次数。if
语句的数量。- 第一个字符串的长度。
- 其他字符串的长度也是恒定的。
所以您是正确的 - 您的函数不使用其输入(args
),因此不依赖于其可扩展性(无论是好是坏)。
然而,这并不意味着O(1)
和O(10000)
运行速度一样快,当然它们都属于相同的复杂性组 - O(1)
,但它们不会在相同的时间内完成运行!
在这里,您正在执行5亿次迭代,检查一个字符串是否包含在另一个字符串中,这当然比执行100万次迭代或1亿次迭代要慢得多,差距大约为(约X500,约X5)。
尽管它们都属于相同的“数学”集合 - O(1)
。
英文:
As the comment by the user Some programmer dude, time complexity is just abstract as it sounds - it does not tell you how long in seconds (or any time measurement in that case) the code will finish running, but to give it an abstract evaluation of how good/worst it handles input according to its size.
Not to mention the actual running time is affected by other factors such as:
- Memory allocation speed
- Clock rate of the CPU
and much more.
The size can be anything you base your methods on: length of an array, length of a string, number of bytes to process etc..
In this case, you measure your O
by the number of iterations you're doing in the for
loop.
Here everything is a constant:
- The number of iterations of the
for-loop
. - Number of
if
statements. - The first string's length.
- Other strings also have constant lengths.
So you're correct - your function does not make any use of its input (args
), thus does not rely on how scalable it is (for good and bad).
However, it does not mean O(1)
runs as fast as O(10000)
, surely they are in the same complexity group - (O(1)
) but they will not finish running at the same time!
Here you're doing 500 million iterations that check if one string is included in the other string, that of-course will be much slower than just doing 1 million iterations, or 100 million iterations, by these according (roughly) factors (~X500, ~X5).
Although they are all in the same "mathematical" set - O(1)
.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论