java – 置换函数的运行时间

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java – 置换函数的运行时间，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1640字，纯文字阅读大概需要3分钟。

内容图文

我的书为一个函数提供了以下代码,该函数计算一串独特字符的所有排列(见下面的代码),并说运行时间是O(n！),“因为有n！排列.”

我不明白他们如何计算运行时间为O(n！).我认为它们的意思是“n”是原始字符串的长度.我认为运行时间应该类似于O((n 1)XY),因为getPerms函数将被调用(n 1)次,并且X和Y可以分别表示外部和内部for循环的运行时间.有人可以向我解释为什么这是错的/本书的答案是对的吗？

谢谢.

public static ArrayList<String> getPerms(String str)
{
    if (str == null)
        return null;

    ArrayList<String> permutations = new ArrayList<String>();

    if (str.length() == 0)
        permutations.add("");
        return permutations;

    char first = str.charAt(0); //first character of string
    String remainder = str.substring(1); //remove first character

    ArrayList<String> words = getPerms(remainder);
    for (String word: words)
    {
        for (i = 0; i <= word.length(); i++)
        {
            String s = insertCharAt(word, first, i);
            permutations.add(s)
        }
    }

    return permutations;

}

public static String insertCharAt(String word, char c, int j)
{
    String start = word.substring(0, i);
    String end = word.substring(i); 
    return start + c + end;
}

资料来源：破解编码面试

解决方法:

从我们的直觉来看,很明显没有现有算法可以生成N个项目的排列,这些项目的性能优于O(n！),因为有n个！可能性.

您可以将递归代码缩减为递归方程,因为gePerm(n)其中n是n长度的字符串将调用getPerm(n-1).然后,我们使用它的所有值返回并放置一个循环N次的内部循环.所以我们有

P_n = nP_n-1
P₁ = 1

很容易看出Pn = n！通过伸缩方程.

如果你很难想象我们如何提出这个等式,你也可以这样思考

ArrayList<String> words = getPerms(remainder);
for (String word: words)                          // P(n-1)
{
    for (i = 0; i <= word.length(); i++)          // nP(n-1)
    {
        String s = insertCharAt(word, first, i);
        permutations.add(s)
    }
}

内容总结

以上是互联网集市为您收集整理的java – 置换函数的运行时间全部内容，希望文章能够帮你解决java – 置换函数的运行时间所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端