该代码列出所有排列的时间复杂度? [英] Time complexity of this code to list all permutations?

问题描述

例如，如果输入字符串为"ABC"，则输出应为"ABC，ACB，BAC，BCA，CAB，CBA".

For example, if the input string is "ABC", then output should be "ABC, ACB, BAC, BCA, CAB, CBA".

这是我的方法:

#include<stdio.h>
#include<conio.h>
#include<string.h>

void print(char str[],int visited[],int index,char temp[],int len)
{



    if(index==len)
    {
        temp[index]='\0';
        printf("\n%s",temp);
        return;
    }


    for(int i=0;i<len;i++)
    {
        if(!visited[str[i]-'A'])
        {
            visited[str[i]-'A']=1;
            temp[index]=str[i];
            print(str,visited,index+1,temp,len);
            visited[str[i]-'A']=0;
        }
    }


}

int main()
{
    int visited[20]={0};
    char temp[20];
    char str[] = "ABCD";
    int len=strlen(str);
    print(str,visited,0,temp,len);

    getch();
    return 0;
}

我已经使用了访问数组来避免重复字符. 该代码的复杂性是什么?

I have made use of a visited array to avoid repetition of characters. What will be the complexity of this code?

推荐答案

如果让n为可用字符的总数，而k为尚未选择的字符数，则可以看到每个函数调用都执行Θ. (n)工作(通过遍历长度为len的数组或打印出长度为len的字符串)，然后生成k个递归调用.每个通话的总工作量始终为&n;(n)，因此我们可以通过查看拨打的总电话数来计算完成的总工作量.

If you let n be the total number of characters available and k be the number of characters not yet picked, then you can see that each function call does Θ(n) work (either by iterating over the array of length len or by printing out a string of length len), then spawns off k recursive calls. The total work done per call is always Θ(n), so we can count the total work done by looking at how many total calls are made.

请注意

• 1个呼叫，其中k = n，
• n个呼叫，其中k = n-1，
• n(n-1)个调用，其中k = n-2，
• n(n-1)(n-2)个呼叫，其中k = n-3，
• ...
• n！ /k！要求任意k

因此总通话次数由总和给出

So the total number of calls is given by the sum

从k = 0到n(n！/k！)的总和

sum from k = 0 to n (n! / k!)

= n！ (总和从k = 0到n(1/k！))

= n! (sum from k = 0 to n (1 / k!))

一个有趣的发现是，这里的总和是e的泰勒展开式(1/0！+ 1/1！+ 1/2！+ 1/3！+ ...)，它被提前截断了一点.因此，随着n变大，渐近进行的呼叫数接近e n！.它的下界也为n !，因此总和为Θ(n！).由于您每次通话都完成了(Then)工作，因此已完成的工作总额为&Theta(n· n！).

An interesting observation is that the summation here is the Taylor expansion for e (1/0! + 1/1! + 1/2! + 1/3! + ... ), truncated a bit early. Therefore, as n gets large, the number of calls made asymptotically approaches e n!. It's also lower-bounded by n!, so this summation is Θ(n!). Since you're done Θ(n) work per call, the total amount of work done is therefore Θ(n · n!).

希望这会有所帮助！

这篇关于该代码列出所有排列的时间复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！