我在 中写了一个递归程序方案 ,而且我无法获得它的时间复杂度。我相信结果是 O(log(n)),但我绝对不是这个时间复杂度的专家。你能帮我试着解决这个问题的复杂性吗?
这是我的伪代码:
function A {
for (int i = 0; i < length.list(); i++)
{
if (list is null)
output absolute value of result
if (s2 < s1)
recall function A, adding item to s2 value.
else
recall function A, adding item to s1 value.
}
}
这是 Scheme 中的实际代码:
(define min-split (lambda (L s1 s2 mini)
(cond
((null? L)
(if (> 0 mini)
(min-split L s1 s2 (- mini (+ mini mini)))
mini
)
mini
)
((> s2 s1)
(min-split (cdr L) (+ s1 (car L)) s2 (- (+ (car L) s1) s2))
)
(else
(min-split (cdr L) s1 (+ s2 (car L)) (- (+ (car L) s2) s1))
)
)
)
)
谢谢!
最佳答案
If-then-else 语句具有恒定顺序,O(1)。
它没关系你有多少嵌套的 if 语句,因为你将编码一个有限的数量,它总是恒定的顺序。
我需要查看更多涉及递归调用的代码,以查看算法的时间复杂度是多少,但 if 语句仅在创建基本情况时有用。它本身不会以任何有意义的方式增加程序的复杂性。
以下面的程序为例:
int foo(List<Integer> bar) {
if (bar.size() == 0)
return -1;
if (bar.size() > 0) {
bar.remove();
return foo(bar);
}
return bar.remove();
}
这个递归程序的运行时复杂度是 O(n),因为通过分析它,我们可以看到正在对 List bar 中的每个项目进行递归调用。
所以,最坏的情况是 O(n) ,因为 foo 最多将被调用次数 n,作为列表的大小。最好的情况是 O(1)。 if 语句本身与复杂性无关。他们只提供基本/递归案例。
关于if-statement - 时间复杂度 : Nested 'if-then-else' ,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34075991/