time-complexity - 如何评估以下代码的渐近复杂度？

Question

我试图掌握如何评估给定一段代码的复杂性。我知道嵌套的 for 循环导致二次复杂度，线性复杂度的 for 循环和恒定复杂度的基本操作。在尝试分析下面的代码时，我认为渐近复杂度是二次的，因为我们嵌套了 for 循环，我真的不知道是否还应该考虑 if 语句，以及复杂性是否甚至可能比二次更差。谁能帮助我指导我如何分析复杂性？

static BST<PathPair, Integer> findSimilarity(BST<Path, Ngram[]> files, BST<Ngram, ArrayList<Path>> index) {
        // TODO: Use index to make this loop much more efficient.
        // N.B. Path is Java's class for representing filenames.
        // PathPair represents a pair of Paths (see PathPair.java).
        BST<PathPair, Integer> similarity = new BST<PathPair, Integer>();
        for (Path path1: files.keys()) {
            for (Path path2: files.keys()) {
                if (path1.equals(path2))
                    continue;

                Ngram[] ngrams1 = files.get(path1);
                Ngram[] ngrams2 = files.get(path2);
                for (Ngram ngram1: ngrams1) {
                    for (Ngram ngram2: ngrams2) {
                        if (ngram1.equals(ngram2)) {
                            PathPair pair = new PathPair(path1, path2);
                            if (!similarity.contains(pair))
                                similarity.put(pair, 0);
                            similarity.put(pair, similarity.get(pair)+1);
                        }
                    }
                }
            }
        }

        return similarity;
    }

提前致谢！

/缺口

标签： time-complexitycomplexity-theory