if-statement - 时间复杂度 : Nested 'if-then-else'

Question

我在 中写了一个递归程序方案 ，而且我无法获得它的时间复杂度。我相信结果是 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))
                      )
                  )
                )
)

谢谢!

Answer 1

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 语句本身与复杂性无关。他们只提供基本/递归案例。