6

私はアルゴリズム分析にかなり精通しており、使用しているほとんどのアルゴリズムのBig-Oを知ることができます。しかし、私が書いたこのコードのBig-Oを思い付くことができず、何時間も立ち往生しています。

基本的には、文字列の順列を生成する方法です。これは、文字列内の各文字を最初の文字にし、それをその文字よりも少ない部分文字列の順列と（再帰的に）組み合わせることによって機能します。

反復回数をカウントするコードを入力すると、O（N！）とO（N ^ N）の間に何かがあります。しかし、私はそれを精神的に分析する方法を理解することができませんでした。どんな提案でも大歓迎です！

import java.util.ArrayList;
import java.util.List;

public class Permutation {

   int count = 0;

   List<String> findPermutations(String str) {
      List<String> permutations = new ArrayList<String>();
      if (str.length() <= 1) { 
         count++;
         permutations.add(str);
         return permutations;
      }
      for (int i = 0; i < str.length(); i++) {
         String sub = str.substring(0, i) + str.substring(i + 1);
         for (String permOfSub : findPermutations(sub)) {
            count++;
            permutations.add(str.charAt(i) + permOfSub);
         }
      }
      return permutations;
   }

   public static void main(String[] args) {
      for (String s : new String[] {"a", "ab", "abc", "abcd", "abcde", "abcdef", "abcdefg", "abcdefgh"}) {
         Permutation p = new Permutation();
         p.findPermutations(s);
         System.out.printf("Count %d vs N! %d%n", p.count, fact(s.length()));
      }
   }

   private static int fact(int i) {
      return i <= 1 ? i : i * fact(i-1);
   }
}

編集1：テストプログラムを追加

編集2：count++ベースケースに追加

4

1 に答える 1

4

漸化式：T(n) = n*(T(n-1) + (n-1)!), T(1) = 1ここでn = str.length。

WolframAlfaは、解はn *（1）nすなわちn*n!。

上記は、すべての文字列操作がO（1）であることを前提としています。それ以外の場合、String sub = ...およびpermutations.add(str.charAt(i) + permOfSub)ラインのコストがO（n）と見なされる場合、方程式は次のようになります。

T(n+1)=(n+1)*(n + T(n) + n!*(n+1))

T（n）〜（n * n + 2 * n-1）* n！すなわち、O(n!*n*n)

于 2012-07-11T04:20:47.213 に答える