Как найти временную сложность в зависимости от заданных параметров - PullRequest
Новая
       14

Как найти временную сложность в зависимости от заданных параметров

0 голосов
/ 19 апреля 2019

Приведенный ниже код служит для счетчика слов , который, учитывая текстовый файл, печатает количество (суммарных и дискретных) слов и перечисляет k наиболее часто используемых слов в порядке убывания на основеуровень использования.

Учитывая это, моя цель состоит в том, чтобы вычислить сложность времени наихудшего случая этого решения как функцию параметров: c ( общее количество символов), m ( общее количество слов ), n ( общее количество дискретных слов ), k ( количество напечатанных слов ).

Пока что мне удалось выяснить только это, поскольку я использую Insertion Sort для сортировки arrayList, содержащего количество использованийдля каждого отдельного слова требуется O (n ^ 2) для этой части и O (k) для печати результатов, но я не могу точно сказать, дали ли эти результаты мои результатыправильно, или как действовать с параметрами c и m .Есть подсказки? 

public static void main(int k)throws IOException{

   //Create input stream & scanner
   FileInputStream fin = new FileInputStream("readwords.txt");
   Scanner fileInput = new Scanner(fin);

   //Create the ArrayLists
   ArrayList<String> words = new ArrayList<String>();
   ArrayList<Integer> totalCount = new ArrayList<Integer>();
   ArrayList<Integer> discreteCount = new ArrayList<Integer>();

   //Read through file and find the words
   while(fileInput.hasNext()){
       //Get the next word
       String nextWord = fileInput.next();
       //Determine if the word is in the ArrayList
       if(words.contains(nextWord)){
           int index = words.indexOf(nextWord);
           discreteCount.set(index, discreteCount.get(index) + 1);
           totalCount.add(1);
        }
        else {
            words.add(nextWord);
            discreteCount.add(1);
            totalCount.add(1);

        }
    }

    //Close
    fileInput.close();
    fin.close();

    //Sort ArrayLists
    InsertionSort.sort(discreteCount, words);

    //Print out the results
    System.out.println("This file contains " +totalCount.size()+" words, There are " +discreteCount.size()+ " discrete words.");
        int i = 1;
        while(i <=discreteCount.size() && i <= k){
            System.out.println(discreteCount.get(discreteCount.size()-i) +" "+words.get(discreteCount.size()-i));
            i ++;
        }   

}
...