Блог

Я застрял на анализе сложности времени выполнения моего решения проблемы класса.

У меня есть большой массив, который представляет сервер, и каждый элемент массива представляет строку терминала. Строка терминала содержит много пользователей и их количество. Моя задача — прочитать файл, содержащий строку чисел и символов в каждой строке, сохранить их в массиве и найти пользователя с наибольшим количеством в каждой строке терминала.

Однако мне трудно определить временную сложность моего решения (класс LineReport). Analyze the big-O CPU performance of LineReport, for N input lines and O(N) different users, and thus O(N) entries on each list once partially done.

 public class LineReport {
    private LineUsage[] lines = new LineUsage[501];
    private String lineInfo = "";
    private int lineNum = 0;
    
    /**
     *  reads a file once per line via command line, splits each line of string
     *  into two parts, line number and username, and feeds the username into 
     *  an array of LineUsage object with line number as the index of array. 
     */
    public void readMessages() {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNextLine()) {
            lineInfo = scan.nextLine();
            String[] temp = new String[2];
            temp = lineInfo.split(" ");
            lineNum = Integer.parseInt(temp[0]);
            if (lines[lineNum] != null) {
                lines[lineNum].addObservation(temp[1]);
            } else {
                lines[lineNum] = new LineUsage();
                lines[lineNum].addObservation(temp[1]);
            }
        }
        scan.close();
    }
    /**
     *  writes the most common user of each terminal line with its count
     *  to console in following format:<br>
     *      Line#   Username    Count<br>
     *      1 amp;emsp;amp;emsp;joe amp;emsp;amp;emsp;amp;emsp; 100
     */
    public void showReport() {
        System.out.println("Line Most Common User Count:n");
        for (int i = 1; i < lines.length; i  ) {
            if (lines[i] != null) {
                Usage maxUsage = lines[i].findMaxUsage();
                System.out.println((i)   " "   maxUsage.getUsername()   " "   maxUsage.getCount());
            } else {
                System.out.println((i)   " NONE 0");
            }
        }
    }
}
 

 public class LineUsage {
    private Map<String, Integer> users;
    
    LineUsage() {
        this.users = new HashMap<String, Integer>();
    }
    
    /**
     *  inserts given string of username into map
     */
    public void addObservation(String username) {
        if (username.length() > 40) {
            throw new IllegalArgumentException("username must be no more than 40 characters");
        }
        if (users.containsKey(username)) {
            users.put(username, users.get(username)   1);
        } else {
            users.put(username, 1);
        }
    }
    
    /** 
     *  iterates through map and find the user with highest count and returns
     *  an instance of Usage object with found user and its count
     *  @return the instant of Usage object with found user and its count
     */
    public Usage findMaxUsage() {
        String maxUser = "";
        int maxCount = 0;
        
        for (String username: users.keySet()) {
            if (users.get(username) > maxCount) {
                maxUser = username;
                maxCount = users.get(username);     
            }
        }
        return new Usage(maxUser, maxCount);
    }
}
 

Мне показалось, что это решение O (n ^ 2). Он имеет два метода readMessages() и showReport() . readMessages() имеет цикл while и метод O (n) split() * так что это n * n = n^2 . showReport() также имеет цикл и метод O (n) addObservation() , который является другим n * n = n^2 . Следовательно, весь класс n^2 n^2 = 2n^2 . Отбросьте константу, и у меня будет сложность O(n^2)

Пожалуйста, поправьте меня, если я в чем-то ошибаюсь. Заранее спасибо.

*https://softwareengineering.stackexchange.com/a/331951

Временная сложность LineReport класса — нет O(n^2) . Временная сложность обоих методов showReport() и readMessages() есть O(n) .

split(String regex) Имеет временную сложность O(n) , где N — количество символов во входной строке. В вашем случае N это не так, N это количество входных строк; каждая такая строка состоит из номера строки и имени пользователя. В split() функции вы передаете каждую такую строку в качестве параметра.

Следовательно, сложность вашего split() метода не равна O (n). Это будет O(k) где k — количество символов во входной строке (не n так, поскольку n в вашем случае уже представляет что-то другое). Следовательно, общая сложность вашего readMessages() метода такова O(n*k) .

Однако, если количество символов не превышает определенного предела, скажем, 100 (что верно в вашем случае, поскольку имя пользователя не может содержать более 40 символов, а номер строки вряд ли будет состоять из k цифр), тогда сложность функции разделения будет O (100), что уменьшится до O (1). Для упрощения, если k не будет превышать определенную константу, независимо от того, каковы входные n данные, тогда сложность уменьшится до O(n) .

Временная сложность метода showReport() равна O (n). В showReport() методе есть for loop , который будет выполняться для n times . На итерации цикла for происходит вызов метода findMaxUsage() , который будет выполняться до тех пор, пока в вашей хэш-карте есть запись.

Для того, чтобы ваш showReport() метод имел сложность O (n ^ 2), количество ключей в каждой хэш-карте, которые представляют количество пользователей в любой конкретной строке, должно быть n. Это невозможно. Попробуйте подумать, почему, и вы поймете, почему общая сложность showReport() is O(n) .

Надеюсь, я вам помог. Прокомментируйте любые дальнейшие проблемы или если вы не можете понять, почему количество пользователей в какой-либо конкретной строке всегда меньше n.