Set操作的复杂性

Question

这就是我在做的事情:
String one ="some string"
String two ="some string"

我想知道字符串一和二中的所有字符,它们应该按顺序排列,因为它们在字符串1中

我编写了一个Java程序,通过使用Collections对集合执行set操作.
我想知道执行集合运算的复杂性是多项式时间还是线性时间

我的节目就在这里

/*
 * 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在必要时删除项目(从ArrayListO(N)中删除,见[1]),得到O(N*(N + M)).

可以通过使用降低复杂度为O(N*M)LinkedList为l_one(因为从去除LinkedList是O(1),参见[2]),并且通过使用进一步将其降低到O(N*日志(M))TreeSet为l_two(自搜索到TreeSetO(log(M)),见[3]).

参考文献:

1. 所有其他操作都以线性时间运行(ArrayListjavadoc)
2. 所有操作都表现为双链表所预期的(LinkedListjavadoc)
3. 此实现为基本操作(add,remove和contains)(TreeSetjavadoc)提供有保证的log(n)时间成本