递归算法的复杂性

Question

我在做一个项目。我需要计算一个递归方法的复杂性。这个方法被递归调用并使用方法“incomingEdges”和“opposite”。有人可以帮助我找到“功能”方法的复杂性吗？

public HashMap<String, Integer[]> FUNCTION() { 

    HashMap<String, Integer[]> times = new HashMap<>(); 
    Integer[] timesAct = new Integer[5]; 
    boolean[] visited = new boolean[graphPertCpm.numVertices()]; 

    Vertex<Activity, String> current = graphPertCpm.getVertex(0); 
    timesAct[0] = 0; 
    timesAct[1] = 0; 
    times.put(current.getElement().getKeyId(), timesAct); 
    FUNCTION(current, times, visited); 

    return times; 
} 

private void FUNCTION(Vertex<Activity, String> current, HashMap<String, Integer[]> times, boolean[] visited) { 

    if (times.get(current.getElement().getKeyId()) == null) { 
     for (Edge<Activity, String> inc : graphPertCpm.incomingEdges(current)) { 
      Vertex<Activity, String> vAdj = graphPertCpm.opposite(current, inc); 
      FUNCTION(vAdj, times, visited); 

     } 
    } 

    visited[current.getKey()] = true; 
    for (Entry<Vertex<Activity, String>, Edge<Activity, String>> outs : current.getOutgoing().entrySet()) { 
     if (!visited[outs.getKey().getKey()]) { 
      int maxEF = 0; 
      Vertex<Activity, String> vAdj = graphPertCpm.opposite(current, outs.getValue()); 
      for (Edge<Activity, String> inc : graphPertCpm.incomingEdges(outs.getKey())) { 
       Integer[] timesAct = times.get(graphPertCpm.opposite(outs.getKey(), inc).getElement().getKeyId()); 
       if (timesAct == null) { 
        vAdj = graphPertCpm.opposite(vAdj, inc); 
        FUNCTION(vAdj, times, visited); 
       } else { 
        if (timesAct[1] > maxEF) { 
         maxEF = timesAct[1]; 
        } 
       } 
      } 
      Integer[] timesAct = new Integer[5]; 
      timesAct[0] = maxEF; 
      timesAct[1] = timesAct[0] + outs.getKey().getElement().getDuration(); 
      times.put(outs.getKey().getElement().getKeyId(), timesAct); 
      if (visited[vAdj.getKey()] != true) { 
       FUNCTION(vAdj, times, visited); 
      } 
     } 
    } 

    visited[current.getKey()] = false; 
} 

对面方法

public Vertex<V, E> opposite(Vertex<V, E> vert, Edge<V, E> e) { 

    if (e.getVDest() == vert) { 
     return e.getVOrig(); 
    } else if (e.getVOrig() == vert) { 
     return e.getVDest(); 
    } 

    return null; 
} 

IncomingEdges方法

public Iterable<Edge<V, E>> incomingEdges(Vertex<V, E> v) { 

    Edge e; 
    ArrayList<Edge<V, E>> edges = new ArrayList<>(); 

     for (int i = 0; i < numVert; i++) { 
      for (int j = 0; j < numVert; j++) { 
       e = getEdge(getVertex(i), getVertex(j)); 
       if (e != null && e.getVDest() == v) { 
        edges.add(e); 

       } 
      } 
     } 


    return edges; 
} 

Answer 1

所以，首先你熟悉大O分析的概念？

计算时间复杂度的最常用指标是大O符号。这消除了所有常数因素，因此当N接近无穷大时，可以根据N估计运行时间。一般来说，你可以认为它是这样的：

常数O（1）

        statement; 

语句的运行时间不会在关系改变为N.

线性O（n）的

     for (i = 0; i < N; i++) 
          statement; 

循环的运行时间与N成正比。当N翻倍时，运行时间也翻倍。

二次O（N 2）

     for (i = 0; i < N; i++) { 
          for (j = 0; j < N; j++) 
           statement; 
         } 

两个环路的运行时间成比例N的平方当N增加一倍，由N * N.

对数澳运行时间的增加（log n）的

while (low <= high) { 
    mid = (low + high)/2; 
if (target < list[mid]) 
    high = mid - 1; 
else if (target > list[mid]) 
    low = mid + 1; 
else break; 
} 

该算法的运行时间成比例的次数N可通过2被划分的数量。这是因为该算法将所述工作区域中的一半使用电子ach迭代。

Linearithmic为O（n log n）的

     void quicksort (int list[], int left, int right){ 
          int pivot = partition (list, left, right); 
          quicksort (list, left, pivot - 1); 
          quicksort (list, pivot + 1, right); 
         } 

就是n *日志（N）。运行时间由对数的N个循环（迭代或递归）组成，因此该算法是线性和对数（也称为linearithmic）的组合。

请注意，这些都没有考虑到最佳，平均和最差情况下的措施。每个人都有自己的Big O符号。还要注意这是一个非常简单的解释。大O是最常见的，但它也更复杂。还有其他符号，如大欧米茄，小o和大θ。在算法分析课程之外，你可能不会遇到它们。

你的函数可以被剥离到两个for-loops与recursive电话和一个额外的for-loop：

for (Edge<Activity, String> inc : graphPertCpm.incomingEdges(current)) { 
      Vertex<Activity, String> vAdj = graphPertCpm.opposite(current, inc); 
      FUNCTION(vAdj, times, visited); 

for (Entry<Vertex<Activity, String>, Edge<Activity, String>> outs : current.getOutgoing().entrySet()) { 

     for (Edge<Activity, String> inc : graphPertCpm.incomingEdges(outs.getKey())) { 

       FUNCTION(vAdj, times, visited); 

随后的建议，咨询主定理

如果你需要的复杂性图表操作，看着Big-O Cheat Sheet收益率