java - 递归算法的复杂性

Question

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

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

那么，首先您是否熟悉 Big-O 分析的概念？

计算时间复杂度的最常用指标是大 O 表示法。这消除了所有常量因素，因此当 N 接近无穷大时，可以根据 N 估计运行时间。一般来说，你可以这样想:

常数 O(1)

                                    statement;

语句的运行时间不会随着N的变化而变化。

线性 O(n)

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

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

二次 O(n2)

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

两个循环的运行时间与N的平方成正比，当N翻倍时，运行时间增加N * N。

对数 O(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 的次数成正比。这是因为算法在每次迭代时将工作区域分成两半。

线性算术 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 * log ( N )。运行时间由对数的N个循环(迭代或递归)组成，因此该算法是线性和对数(也称为线性)的组合。

请注意，所有这些都没有考虑最佳、平均和最坏情况的衡量标准。每个都有自己的大 O 符号。另请注意，这是一个非常简单的解释。大 O 是最常见的，但它也比我展示的更复杂。还有其他符号，例如 big omega、little o 和 big theta。在算法分析类(class)之外，您可能不会遇到它们。

您的函数可以通过 递归 调用和一个额外的 for 循环 精简为两个 for 循环:

 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产量