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

Question

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

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);  
}

}

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

Answer 1

时间复杂度如下

1. 每次初始化的复杂度为 O(1)
2. 每个循环复杂度为O(n)
3. 每个嵌套循环的复杂度为 O(n^2)
4. 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