时间复杂度：嵌套 '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 语句并不重要，因为您将编写有限数量的代码，它始终是恒定顺序。

我需要查看更多涉及递归调用的代码才能了解算法的时间复杂度，但 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)，因为在分析它时，我们可以看到对列表中的每个项目都进行了递归调用，bar。

因此，最坏的情况是 O(n)，因为 foo 最多将被调用次数 n，作为列表的大小。最好的情况是 O(1)。 if 语句本身与复杂性无关。他们只提供基本/递归情况。

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

Time Complexity: Nested 'if-then-else'

time

complexity-theory

big-o

if-statement