如何找到算法的时间复杂度 [英] How to find time complexity of an algorithm
问题描述
问题
如何查找算法的时间复杂度？
How to find time complexity of an algorithm?
在发布SO问题之前我做了什么？
我经历过此，
I have gone through this, this and many other links
但是没有找到关于如何计算时间复杂度的清晰直接的解释。
But no where I was able to find a clear and straight forward explanation for how to calculate time complexity.
我知道什么？
说出与以下代码一样简单的代码：
Say for a code as simple as the one below:
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 而不是声明。
i < N; 这将被执行 N + 1 次
i ++; 这将被执行 N 次
因此此循环所需的操作次数为
So the number of operations required by this loop are
{1+（N + 1）+ N} = 2N + 2
注意：这仍然可能是错误的，因为我对自己的信心不强对计算时间复杂度的理解
Note: This still may be wrong, as I am not confident about my understanding on calculating time complexity
我想知道什么？
好，因此，我想我知道这些小的基本计算，但是在大多数情况下，我将时间复杂度视为
Ok, so these small basic calculations I think I know, but in most cases I have seen the time complexity as
O（N），O（n2），O （log n），O（n！） ....以及许多其他 ，
O(N), O(n2), O(log n), O(n!).... and many other,
谁能帮助我理解一个算法的时间复杂度如何计算？我肯定会有像我这样的新手。
Can anyone help me understand how does one calculate time complexity of an algorithm? I am sure there are plenty of newbies like me wanting to know this.
推荐答案
如何查找算法的时间复杂度
How to find time complexity of an algorithm
您将根据输入大小来执行多少条机器指令，然后将表达式简化为最大的项（当N非常大时），并且可以包括任何简化的常数因子。
You add up how many machine instructions it will execute as a function of the size of its input, and then simplify the expression to the largest (when N is very large) term and can include any simplifying constant factor.
例如，让我们看看如何简化 2N + 2 机器指令将其描述为 O（N）。
For example, lets see how we simplify 2N + 2 machine instructions to describe this as just O(N).
为什么要删除两个 2 ？
Why do we remove the two 2s ?
我们对当N变大时，算法的性能。
We are interested in the performance of the algorithm as N becomes large.
考虑两个项2N和2。
什么是随着N变大，这两个项的相对影响是什么？假设N是一百万。
What is the relative influence of these two terms as N becomes large? Suppose N is a million.
然后，第一项为200万，第二项仅为2。
Then the first term is 2 million and the second term is only 2.
出于这个原因，我们删除了除大数N之外的所有最大项。
For this reason, we drop all but the largest terms for large N.
因此，现在我们从 2N + 2 到 2N 。
传统上，我们只对直到恒定因子的性能感兴趣。
Traditionally, we are only interested in performance up to constant factors.
这意味着当N很大时，我们实际上并不关心性能差异是否存在恒定的倍数。最初，2N的单位定义不明确。因此，我们可以将其乘以或除以一个常数因子来得出最简单的表达式。
This means that we don't really care if there is some constant multiple of difference in performance when N is large. The unit of 2N is not well-defined in the first place anyway. So we can multiply or divide by a constant factor to get to the simplest expression.
所以 2N 变成 N 。
这篇关于如何找到算法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
