在 for 循环时间和 space 复杂度中嵌套 Collection.stream()

Question

我有一个算法，我需要找到它的 space 和时间复杂度。

public static List<Integer> myList(String niceKeys, String badKeys,
                                                List<Integer> myIds,
                                                List<String> reviews, int k) {
        List<String> niceKeyToken = Arrays.asList(niceKeys.split(" "));
        List<String> badKeyToken = Arrays.asList(badKeys.split(" "));
        Map<Integer, Integer> niceReview = new HashMap<>();
        for (int i = 0; i < reviews.size(); i++) {
            int myId = myIds.get(i);
            List<String> review = Arrays.asList(reviews.get(i).split(" "));
            int currentNice = (int) review.stream()
                    .filter(token -> niceKeyToken.contains(token))
                    .count();
            int currentBad = (int) review.stream()
                    .filter(token -> badKeyToken.contains(token))
                    .count();
            int total = currentNice * 3 + currentBad * -1;
            int previous = niceReview.getOrDefault(myId, 0);
            niceReview.put(myId, previous + total);
        }
        List<Integer> finalList = niceReview.entrySet()
                .stream()
                .sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
                .limit(k)
                .map(Map.Entry::getKey)
                .collect(Collectors.toList());
        return finalList;
    }

如果评论的大小是 M，它应该是 O(M)。但是然后我们在 for loop 里面做 review.stream() 这应该会增加复杂性但我不确定有多少？ space 复杂度是多少？

任何帮助将不胜感激。

Answer 1

如果评论大小为 M，假设评论大小为 N，niceKeyToken - X，badKeyToken - Y，时间复杂度应为 O(M * (N * X + N * Y))，我不太确定关于 space 的复杂性，您正在使用字符串，所以我想说这取决于字符串的大小。我认为最好用大测试数据做一些基准测试。

首先关于 niceKeyToken 和 badKeyToken - 您仅将它们用于搜索，因此 List 不是数据结构的最佳选择，您应该使用 HashSet。 ArrayList.contains() 的时间复杂度为 O(N)，而 HashSet - O(1).

其次关于流 - 您正在流式传输评论列表两次，一次用于好的密钥，然后两次用于坏的密钥。你只是对流进行简单的过滤，我认为流对于这种情况来说是一种矫枉过正，你可以通过一个循环来逃脱。流有时可能很昂贵而且很慢（同样最好进行基准测试）。

第三点源于第二点——评论不需要保存在列表中，如果你只是迭代它，一个数组就足够了。

我会这样做：

public static List<Integer> myList(String niceKeys, String badKeys, List<Integer> myIds, List<String> reviews, int k) {
        //HashSet contains method returns in constant time, for list, if the element, you are looking for is last
        //potentially you have to traverse entire collection
        Set<String> niceKeyToken = new HashSet<>(Arrays.asList(niceKeys.split(" ")));
        Set<String> badKeyToken = new HashSet<>(Arrays.asList(badKeys.split(" ")));
        Map<Integer, Integer> niceReview = new HashMap<>();
        for (int i = 0; i < reviews.size(); i++) {
          int myId = myIds.get(i);
          //array would suffice here, only iterating the elements
          String[] review = reviews.get(i).split(" ");
          int currentNice = 0;
          int currentBad = 0;
          //single iteration, instead of twice with streams
          for (int j = 0; j < review.length; j++) {
            String token = review[j];
            //quick lookup for token, because of HashSet
            if (niceKeyToken.contains(token)) {
              currentNice++;
            }
            //quick lookup for token, because of HashSet
            if (badKeyToken.contains(token)) {
              currentBad++;
            }
          }
          int total = currentNice * 3 + currentBad * -1;
          int previous = niceReview.getOrDefault(myId, 0);
          niceReview.put(myId, previous + total);
        }
        return niceReview.entrySet()
                .stream()
                .sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
                .limit(k)
                .map(Map.Entry::getKey)
                .collect(Collectors.toList());
      }

这应该可以将时间复杂度降低到 O(M * N)。

在 for 循环时间和 space 复杂度中嵌套 Collection.stream()

Nested Collection.stream() in for loop time and space complexity

java

time-complexity

space-complexity