java - 集合操作的复杂性

Question

这就是我正在做的:
字符串一 = "一些字符串"
字符串二 = "一些字符串"

我想知道字符串 one 和 two 中的所有字符，它们应该按照字符串 1 中的顺序排列

我写了一个 Java 程序，它通过使用集合对两个集合执行集合操作。
我想知道执行集合运算的复杂度是多少，是多项式时间还是线性时间

我的程序在这里

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package careercup.google;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

/**
 *
 * @author learner
 */
public class CharaterStringsIntersection {
    private static final String one = "abcdefgabcfmnx";
    private static final String two = "xbcg";

    public static void main(String args[]){
        List<Character> l_one = new ArrayList<Character>();
        List<Character> l_two = new ArrayList<Character>();

        for(int i=0; i<one.length(); i++){
           l_one.add(one.charAt(i));
        }
        for(int j=0; j<two.length(); j++){
            l_two.add(two.charAt(j));
        }

        l_one.retainAll(l_two);

        Iterator iter = l_one.iterator();
        while(iter.hasNext()){
            System.out.println(" > " + iter.next());
        }
    }
}

输出:

run:
 > b
 > c
 > g
 > b
 > c
 > x

Answer 1

其复杂度为 O(N * (N + M))，其中 N = one.length()，M = two.length()。

它的工作方式如下:对于 l_one 的每个字符(有 N 个字符)，它会扫描 l_two(因为 l_two 是一个 ArrayList，扫描是线性的，所以它需要 O(M) 步，见 [1])并在必要时从 l_one 中删除项目(从 ArrayList 需要 O(N)，见 [1])，所以你得到 O(N * (N + M))。

您可以通过对 l_one 使用 LinkedList 将复杂度降低到 O(N * M)(因为从 LinkedList 中删除是 O(1 ), 参见 [2]), 以及进一步 通过对 l_two 使用 TreeSet 将其降低到 O(N * log(M))(因为在 TreeSet 中搜索需要 O(log(M) ), 参见 [3]).

引用资料:

1. 所有其他操作都在线性时间内运行 ( ArrayList javadoc )
2. 所有操作的执行都符合双向链表的预期，( LinkedList javadoc )
3. 此实现为基本操作(添加、删除 和包含)提供有保证的 log(n) 时间成本 ( TreeSet javadoc )