时间复杂度：嵌套“if-then-else”

Question

我已经在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))
                      )
                  )
                )
)

谢谢！

Answer 1

If-then-else 语句具有恒定顺序，O(1)。

这不要紧，如果语句你有多少嵌套的，因为你已经编写了一个有限的数量，这始终是恒定的顺序。

我需要查看更多涉及递归调用的代码，以了解算法的时间复杂度是多少，但 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 语句本身与复杂性无关。他们只提供基本/递归案例。