集合运算的复杂性

这就是我正在做的：
字符串一=“某个字符串”
字符串二 =“某个字符串”

我想知道字符串中的所有字符one and two它们应该按第一串中的顺序排列

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

我的程序在这里

/*
 * 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());
        }
    }
}

Output :

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

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

它的工作方式如下：对于每个字符l_one（有 N 个）它扫描l_two (since l_two is an ArrayList，扫描是线性的，因此需要 O(M) 步骤，请参阅[1]）并从l_one如有必要（从ArrayList需要 O(N)，请参阅 [1]），因此您得到 O(N * (N + M))。

您可以使用以下方法将复杂度降低到 O(N * M)LinkedList for l_one（自从删除LinkedList是 O(1)，参见[2]），并且进一步 通过使用将其降低到 O(N * log(M))TreeSet for l_two（自从搜索TreeSet需要 O(log(M))，参见 [3]）。

参考：

1. 所有其他操作都以线性时间运行 (ArrayList javadoc http://download.oracle.com/javase/1.5.0/docs/api/java/util/ArrayList.html)
2. 所有操作都按照双向链表的预期执行, (LinkedList javadoc http://download.oracle.com/javase/1.5.0/docs/api/java/util/LinkedList.html)
3. 此实现为基本操作提供了有保证的 log(n) 时间成本（add, remove and contains) (TreeSet javadoc http://download.oracle.com/javase/1.5.0/docs/api/java/util/TreeSet.html)