相关疑难解决方法(0)

我更喜欢尽可能少的正式定义和简单的数学.

大多数拥有CS学位的人肯定会知道Big O代表什么.它可以帮助我们衡量算法的实际效率(如何),如果你知道你试图解决的问题属于哪个类别,你可以弄清楚是否仍然可以挤出那么少的额外性能.¹

但我很好奇,你如何计算或近似算法的复杂性？

¹ _{但正如他们所说,不要过度,过早优化是所有邪恶的根源,没有正当理由的优化也应该得到这个名称.}

问题

如何找到算法的时间复杂度？

在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

注意:这仍然可能是错误的,因为我对计算时间复杂度的理解没有信心

我想知道什么？ …

证明

1 + 1/2 + 1/3 + ... + 1/n is O(log n). 
Assume n = 2^k

我把这个系列放到了总和中,但我不知道如何解决这个问题.任何帮助表示赞赏

这是伪代码.我试图计算这个函数的时间复杂度,正如这个答案所说的那样.应该是这样的:

n + n/3 + n/9 + ... 

也许时间的复杂性就像O(nlog(n))我猜的那样？或者log(n)应该是log(n) 基数3？有人说时间复杂度是O(n),这对我来说是完全不可接受的.

j = n
while j >= 1 {
    for i = 1 to j {
        x += 1
    }
    j /= 3
}