该算法的运行时间

我有这个算法，我不知道它的时间复杂度是什么。在该算法的运行时间

int oc(int n) { 
    if (n == 0) 
    { 
     return 0; 
    } 
    int s = p[n][0]; 
    for (int i = n-1; i > 0; i--) 
    { 
     int a = p[n][i] + oc(i); 
     if (s > a) 
     { 
      s = a; 

     } 
    } 
    return s; 
}

我假设有（N-1）迭代的for循环，但可以弄清楚什么是总运行时间使用递归的时候。

来源

2016-11-09 Pierre P.

（这是一个_procedure_。要做一个_algorithm_，程序必须解决问题。） – greybeard

让T(n)是计算oc(n)的复杂性。由于用于计算oc(n)您从n-1运行for循环1和递归调用oc(i)，因此

T(n)=T(n-1)+T(n-2)+...+T(1) (*).

相反，如果在T（N-1）我们把

T(n-1)=T(n-2)+T(n-3)+...+T(1)

在(*)平等我们将得到：

T(n)=2*(T(n-2)+...+T(1))

如果我们继续同迭代T(n-2)，T(n-3)等。我们将结束下列等式：

T(n)=2*(T(n-2)+...+T(1)) 
=4*(T(n-3)+...+T(1)) 
=2^i*(T(n-i-1)+...+T(1)) 
=2^n*T(1)/2=O(2^n).

这种复杂性的原因是 - 你的算法计算同样的事情很多次。如果您记住已计算oc函数值的数组中的值，并在函数的第一部分中添加一个检查，该函数将直接从数组中返回值（如果已计算），而不是运行循环，然后再次执行同样的工作，你算法的复杂性将会急剧变化，并且将会是O(n)，因为算法会在你的循环第一次迭代时计算所有的值并存储。

来源

2016-11-09 23:57:25 simon

谢谢你的回答！使用记忆法最多能达到O（n）时间复杂度的适当算法是什么？ –

@PierrePasquet记忆技术非常易于使用，并且您的算法非常适合，您只需要在oc函数中引入2个数组并将它们作为参数传递给oc：memo_oc int []和flag_oc bool []。 Init flag_oc带有错误值，即，我们没有任何记忆/计算的oc值用于重用。设置flag_oc [0] = true和memo_oc [0] = 0。将if（n == 0）{...}条件替换为if（flag_oc [n]）{return memo_oc [n];}并插入“flag_oc [n] = true; memo_oc [n] = s;” “return s;”之前的代码行 – simon

它是O（2 ⁿ）。见迭代次数如何增加ň积聚：

n | f(n) = total iterations 
---+------------------------------------------------- 
1 | 0 
2 | 1 + f(1) = 1 + 0 = 1 
3 | 2 + f(2) + f(1) = 1 + 2f(2) = 1 + 2.1 = 3 
4 | 3 + f(3) + f(2) + f(1) = 1 + 2f(3) = 1 + 2.3 = 7 
...| ... 
n | .... 1 + 2.f(n-1) = 2^(n-1) - 1

来源

2016-11-09 23:49:01 trincot

该算法的运行时间

回答

相关问题