Worst Case Продолжительность

Question

У меня есть следующий фрагмент кода:

public static boolean sumSearch(int[] a, int n, int x) { 
    if (n == 0) { 
     return (x==0); 
    } 
    return (sumSearch(a, n-1, x-a[n-1]) || sumSearch(a, n-1, x)); 

Так от того, что я собираю ... делает третий параметр даже имеет значения? Поскольку return x == 0 не имеет значения для наихудшего случая, это будут вызовы O (n), поскольку n-1 выполняется так, что худшая временная сложность может быть только O (n)? Это правильная линия мышления?

Answer 1

Ну, учитывая, что этот тип проблемы NP-Complete, я думаю, что мы можем исключить временную сложность O (n). Я думаю, что этот алгоритм имеет наихудшее время O (2^n). Если вы представляете вызовы, подобные дереву, каждый «уровень» дерева имеет в два раза больше вызовов, чем уровень перед ним, который, конечно же, выходит на O (2^n).