Java：プログラムの複雑さを計算するには？

Question

私は以下のプログラムを持っています。複数の機能を持っている場合、それぞれの時間複雑さを組み合わせるのか、それとも最高の時間複雑性をすべて取り除くのですか？

私はfind()がnの時間複雑さを持ち、isCompoundがnの時間複雑性を持っていると信じています。あれは正しいですか？

ありがとうございます。投票して回答を受け入れるようにしてください。

private static String[] find(String[] array) { 
    Set<String> words = new LinkedHashSet<>(Arrays.asList(array)); 
    Set<String> otherWords = new HashSet<>(words); 
    for (Iterator<String> i = words.iterator(); i.hasNext();) { 
     String next = i.next(); 
     otherWords.remove(next); 
     if (isCompound(next, otherWords)) { 
      i.remove(); 
     } else { 
      otherWords.add(next); 
     } 
    } 
} 

private static boolean isCompound(String string, Set<String> otherWords) { 
    if (otherWords.contains(string)) { 
     return true; 
    } 
    for (String word : otherWords) { 
     if (string.startsWith(word)) { 
      return isCompound(string.replaceAll("^" + word, ""), otherWords); 
     } 
     if (string.endsWith(word)) { 
      return isCompound(string.replaceAll(word + "$", ""), otherWords); 
     } 
    } 
    return false; 
} 

Answer 1

プログラムの複雑さのようなものはありません。我々はアルゴリズムの時間複雑度を計算するか、またはプログラミングの文脈において、個々の（原子）関数の時間複雑さを計算する。

私たちは、プロファイラのようなツールで実行時間を測定することにより、複数の機能で構成されたプログラムをベンチマークします。 プログラムに何百ものソースファイルが含まれている場合、どのように時間の複雑さを計算することができますか？ findとisCompoundのための複雑性を分析するために

、我々は確かにotherWords.remove(next)、otherWords.add(next)、string.replaceAll("^" + word, "")またはotherWords.contains(string)のように、それらの内部で呼び出される関数のための複雑さを知っておく必要があります。

複雑さが何であるかが分かっている場合は、関数の複雑さを計算できます。すべての複雑さを計算したとしても、それは非常に大きな入力に対して行われる近似にすぎません。だから、あなたは本当に計算したいものを決めます。

編集：プログラムの複雑さを計算するには、呼び出された各ライブラリ関数を分解し、それらを解析することをお勧めします。たとえば、otherWordsはHashSetであるため、otherWords.contains(string)（ハッシュテーブルの検索操作）にはO(1)（big-O）の時間がかかる可能性があります。