程序的最大符号是什么？

Question

我正在尝试确定该程序的算法复杂性：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class SuffixArray
{
    private String[] text;
    private int length;
    private int[] index;
    private String[] suffix;
 
    public SuffixArray(String text)
    {
        this.text = new String[text.length()]; 
 
        for (int i = 0; i < text.length(); i++)
        {
            this.text[i] = text.substring(i, i+1);
        } 
 
        this.length = text.length();
        this.index = new int[length];
        for (int i = 0; i < length; i++)
        {
            index[i] = i;
        } 
 
        suffix = new String[length];
    }
 
    public void createSuffixArray()
    {   
        for(int index = 0; index < length; index++) 
        {
            String text = "";
            for (int text_index = index; text_index < length; text_index++)
            {
                text+=this.text[text_index];
            } 
            suffix[index] = text;
        }
 
        int back;
        for (int iteration = 1; iteration < length; iteration++)
        {
            String key = suffix[iteration];
            int keyindex = index[iteration];
 
            for (back = iteration - 1; back >= 0; back--)
            {
                if (suffix[back].compareTo(key) > 0)
                {
                    suffix[back + 1] = suffix[back];
                    index[back + 1] = index[back];
                }
                else
                {
                    break;
                }
            }
            suffix[ back + 1 ] = key;
            index[back + 1 ] = keyindex;
        }
 
        System.out.println("SUFFIX \t INDEX");
        for (int iterate = 0; iterate < length; iterate++)
        {  
            System.out.println(suffix[iterate] + "\t" + index[iterate]);
        }
    }
 
 
    public static void main(String...arg)throws IOException
    {
        String text = "";
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter the Text String ");
        text = reader.readLine();
 
        SuffixArray suffixarray = new SuffixArray(text);
        suffixarray.createSuffixArray();
    } 
}

我对Wikipedia进行了一些有关Big-O符号的研究，并使用不同尺寸的字符串运行代码。根据用不同尺寸的刺激来运行代码所需的时间，我认为它的复杂性可能为O（n^2）。我怎么知道？

任何帮助将不胜感激。

Answer 1

创建的复杂性方法是o（n^2），您可以通过检查3个循环块来确定这一点。另外，由于在您的问题中，您说过，您已经阅读了Wikipedia文章，其中涵盖了Big-O符号，然后专注于其属性。它们是如何应用正确逻辑并计算算法的复杂性的核心。

在您的第一个块中，最内向的循环迭代长度又重复长度次，由于product，因此产生O（n^2）的复杂性属性 big-o符号的。

for(int index = 0; index < length; index++) 
{
    String text = "";
    for (int text_index = index; text_index < length; text_index++)
    {
        text+=this.text[text_index];
    } 
    suffix[index] = text;
}

在您的第二个区块中，尽管最内向的循环在开始时没有执行长度迭代，但其复杂性仍然倾向于O（n），由于o（n^2）的总体复杂性再次产生产品属性。

for (int iteration = 1; iteration < length; iteration++)
{
    String key = suffix[iteration];
    int keyindex = index[iteration];

    for (back = iteration - 1; back >= 0; back--)
    {
        if (suffix[back].compareTo(key) > 0)
        {
            suffix[back + 1] = suffix[back];
            index[back + 1] = index[back];
        }
        else
        {
            break;
        }
    }
    suffix[ back + 1 ] = key;
    index[back + 1 ] = keyindex;
}

您的第三个也是最后一个块简单地迭代长度次，给我们O（n）的线性复杂性。

for (int iterate = 0; iterate < length; iterate++)
{  
    System.out.println(suffix[iterate] + "\t" + index[iterate]);
}

在此时，要获得方法复杂性，我们需要收集我们拥有的3个子复合物，并将其应用于他们sum属性，这将产生O（n^2）。