java - 如何找到这段代码的时间和空间复杂度？

我已经实现了一个代码来构造模式计数树。我如何找到它的时间和空间复杂度？

class PCTree
{
public static void main(String args[])throws IOException
{
 BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
 int n;//No of Patterns
 int f;//No of Features
 float initial_no_of_nodes=0;//No of Nodes in Input Patterns
 float final_no_of_nodes=0;//No of Nodes in PC Tree(Output)
 float compression_rate;//percentage compression

 System.out.println("Enter No of Patterns:");
 n=Integer.parseInt(input.readLine());

 //2-D array to store Features
 int pattern[][]= new int[n][20];

//No of Features for each Pattern
 for(int i=0;i<n;i++)//NO of Features for each Pattern
 {
     System.out.println("Enter No of Features for Pattern "+(i+1)+" : ");
     f=Integer.parseInt(input.readLine());
     pattern[i]=new int[f];
 }

//Features of each pattern
for(int i=0;i<n;i++)
 {
    System.out.println("Enter Features for Pattern "+(i+1)+" : ");
    for(int j=0;j<pattern[i].length;j++)
    {
    pattern[i][j]=Integer.parseInt(input.readLine());
    }
 }


 System.out.println("==============");
 System.out.println("INPUT ");
 System.out.println("==============");

//Print Features of each pattern
for(int i=0;i<n;i++)
 {

    for(int j=0;j<pattern[i].length;j++)
    {
    System.out.print(" "+pattern[i][j]+" ");
    initial_no_of_nodes++;
    }
    System.out.println();
 }
 System.out.println("\nNODES: "+initial_no_of_nodes);//Print Initial No of Nodes
 System.out.println();
 System.out.println();
 System.out.println("==============");
 System.out.println("PC TREE ");
 System.out.println("==============");

 //Construction of PC Tree
 //Print First Pattern as it is
 for(int j=0;j<pattern[0].length;j++)
    {
    System.out.print(" "+pattern[0][j]+" ");
    final_no_of_nodes++;
    }
    System.out.println();

    int i=0;//processing pattern
    int k=0;//processing features
    int j=1;//processing pattern


while((i<=(n-1))&&(j<n))//Loop works till last pattern is processed
{
   inner: //performs matching of Features
   while(k<pattern[j].length)
    {
    if (pattern[i][k]==pattern[j][k])//Equal Prefix Found
        {
        System.out.print(" _ ");//Print "Blank" Indicate sharing
        k++;
        }
    else//Prefix not equal
     {

        for(int p=k;p<pattern[j].length;p++)//print all features(suffix)
        {
        System.out.print(" "+pattern[j][p]+" ");
        final_no_of_nodes++;
        }
        i++;//next pattern
        j++;//next pattern
        k=0;//start again from first feature
        break inner;//go to next pattern
     }
    }
    System.out.println();

}
 System.out.println("\nNODES: "+final_no_of_nodes);
 compression_rate=((initial_no_of_nodes-final_no_of_nodes)/initial_no_of_nodes)*100;
 System.out.println();
 System.out.println("COMPRESSION RATE: "+compression_rate);
}

}

我如何找到它的时间和空间复杂度？

最佳答案

时间复杂度如下

O(1) 每次初始化

O(n) 对于每个循环

O(n^2) 对于每个嵌套循环

O(n^3) 用于嵌套循环中的 if 条件

对于这部分代码

 BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
 int n;//No of Patterns
 int f;//No of Features
 float initial_no_of_nodes=0;//No of Nodes in Input Patterns
 float final_no_of_nodes=0;//No of Nodes in PC Tree(Output)
 float compression_rate;//percentage compression

 System.out.println("Enter No of Patterns:");
 n=Integer.parseInt(input.readLine());

 //2-D array to store Features
 int pattern[][]= new int[n][20];

复杂性只是初始化时的语句数

for(int i=0;i<n;i++)
 {
    System.out.println("Enter Features for Pattern "+(i+1)+" : ");
    for(int j=0;j<pattern[i].length;j++)
 {
    pattern[i][j]=Integer.parseInt(input.readLine());
    }
  }

复杂度为 O(n^2)

for(int j=0;j<pattern[0].length;j++)
    {
    System.out.print(" "+pattern[0][j]+" ");
    final_no_of_nodes++;
    }

复杂度为 O(n)

while((i<=(n-1))&&(j<n))//Loop works till last pattern is processed
{
   inner: //performs matching of Features
   while(k<pattern[j].length)
    {
    if (pattern[i][k]==pattern[j][k])//Equal Prefix Found
        {
        System.out.print(" _ ");//Print "Blank" Indicate sharing
        k++;
        }

复杂度为 O(n^3)

以及其他语句的复杂性，每个语句的复杂性为 O(1)

所以复杂度为 n+n^2+n^3

所以使用条件 n^3 >> n 和 n^3 >> n^2 复杂度将是 O(n^3)

空间复杂度可以计算为

Type        Typical Bit Width
char            1byte
unsigned char   1byte
signed char     1byte
int             4bytes
unsigned int    4bytes
signed int      4bytes
short int       2bytes
long int        4bytes

关于java - 如何找到这段代码的时间和空间复杂度？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23116379/