时间复杂性：嵌套'if

时间复杂性：嵌套'if-then-else'(Time Complexity: Nested 'if-then-else')

我在Scheme中编写了一个递归程序，我很难得到它的时间复杂度。 我相信它是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)) ) ) ) )

谢谢！

I've written a recursive program in Scheme, and I'm having trouble getting the time complexity of it. I believe it goes out to be O(log(n)), but I am definitely no expert on this time complexity. Can you help me try and work out the complexity of this?

Here's my pseudo-code:

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. } }

Here's the actual code in 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)) ) ) ) )

Thanks!

最满意答案

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-then-else statements are of constant order, O(1).

It doesn't matter how many nested if-statements you have, because you will have coded a finite amount, which is always constant order.

I would need to see more code involving your recursive call to see what the time complexity of the algorithm is, but the if-statement is only useful in creating a base case. It doesn't in itself contribute to the complexity of your program in any meaningful way.

---

Take for example the following program:

int foo(List<Integer> bar) { if (bar.size() == 0) return -1; if (bar.size() > 0) { bar.remove(); return foo(bar); } return bar.remove(); }

The runtime complexity of this recursive program is O(n) because, upon analyzing it, we can see that a recursive call is being made for each item in our List, bar.

So, the worst-case is O(n), because foo will be called at most the number of times, n, as the size of the list. The best-case is O(1). The if statements have no bearing on the complexity in themselves. They only supply the base / recursive case.