我的程序的时间复杂度是多少？

Question

我一直在分析我解决 class 问题的运行时复杂性。

我有一个代表服务器的大数组，数组的每个元素代表一个终端线。终端线路拥有许多用户及其计数。我的工作是读取一个文件，每行包含一串数字和字符，将它们存储在数组中，并在每个终端行找到计数最高的用户。

但是，我很难确定我的解决方案的时间复杂度 (LineReport class)。 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 &emsp;&emsp;joe &emsp;&emsp;&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。因此，整个class就是n^2 + n^2 = 2n^2。去掉常量，我的复杂度为 O(n^2)

如有错误请指正。提前致谢。

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

Answer 1

LineReportclass的时间复杂度是不是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)。为简化起见，如果无论输入 n 是什么，k 都不会超过特定常数，那么复杂度将降低为 O(n).

方法showReport()的时间复杂度是O(n)。在 showReport() 方法中，有一个 for loop 将运行 for n times。在 for 循环的迭代中，会调用方法 findMaxUsage()、，只要您的 hashMap.[= 中有一个条目，该方法就会运行 36=]

为了让你的showReport()方法复杂度为O(n^2)，eachhashMap中key的个数，代表的个数任何特定行中的用户应该是 n。 这是不可能的。试着想想为什么，你就会明白为什么 showReport() 的整体复杂度是 O(n).

希望对您有所帮助。对任何进一步的问题发表评论，或者如果您无法理解为什么任何特定行中的用户数量总是小于 n。

我的程序的时间复杂度是多少？

What is the time complexity of my program?

java

algorithm

performance

big-o

time-complexity