gpt4 book ai didi

algorithm - 这个算法的复杂度(Big-O)是多少?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:41:43 24 4
gpt4 key购买 nike

我对算法分析相当熟悉,并且可以说出我使用的大多数算法的 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++

最佳答案

递归方程:T(n) = n*(T(n-1) + (n-1)!), T(1) = 1 其中 n = str .length.

WolframAlfa 说解是 n*(1)nn*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)

关于algorithm - 这个算法的复杂度(Big-O)是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11425344/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com