java很难找到时间复杂性

Question

我刚刚解决了一个关于leetcode的问题，要求我找到一个给定目标的数字总和。我刚刚解决了它，但我很难找到它的时间复杂性。请帮忙

import java.util.*;
class Solution
{
    List<List<Integer>> result=new ArrayList();
    public List<List<Integer>> combinationSum2(int[] candidates, int target)
    {
        HashMap<List<Integer>,Integer> map=new HashMap();
        List<Integer> temp=new ArrayList();
        Arrays.sort(candidates);
        help(candidates,0,target,map,temp);
        return result;
    }
    private void help(int[] arr,int start,int target,HashMap<List<Integer>,Integer> storage,List<Integer> temp)
    {
        if(start>=arr.length)
            return;
        List<Integer> check=new ArrayList<>(temp);
        check.add(arr[start]);
        if(arr[start]==target)
        {

            if(storage.containsKey(check))
            {
                help(arr,start+1,target,storage,temp);
                return;
            }
            else
            {
                temp.add(arr[start]);
                result.add(temp);
                storage.put(temp,1);
                return;
            }
        }
        if(arr[start]>target)
        {
            return;
        }
        help(arr,start+1,target,storage,temp);
        help(arr,start+1,target-arr[start],storage,check);

    }
}

Answer 1

您通常有1Arrays.sort(candidates)个O(nlog(n))。您还有1个递归调用和2个调用，它应该是O(2^n)。因此，更糟糕的情况应该是O(2^n)

（O1）一个算法被称为运行恒定时间，而不管我们称之为O（1）的输入大小

    int getFirst(int[] arr) {
       return arr[0]; //O(1)
    }

    Map<Integer, Integer> map = new HashMap(){{
      put(1, 10);
    }};

    map.get(1); //O(1)

O（n），如果它运行线性时间

      int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += n[i];
        }

O（logN）以对数计时运行

类似二进制搜索https://en.wikipedia.org/wiki/Binary_search_algorithm

O（n^2）2循环嵌套。 更多的嵌套迭代将导致O（n^3）O（n^4）

for(int i = 0; i < n; i++) {
   for (int j = i; j < n; j++) {
      ...
  }
}

O（2^n）它随着输入的每一个加法而成倍增长

public int fibo(int n) {
    if (n < 2) return n;
    return fibo(n - 2) + fibo(n - 1);
}