Set操作的复杂性
这是我在做什么：
字符串一个=“一些字符串”
String中的两个=“一些字符串”Set操作的复杂性
我想知道的一切都在字符串中的字符一个和两个和他们应该按顺序排列，因为他们在字符串之一
我写了一个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
其复杂度为O（N *（N + M）），其中N = one.length()，M = two.length()。
它工作在以下方式：用于l_one每个字符（有它们的N）它扫描l_two（因为l_two是ArrayList，扫描是线性的，所以它需要O（M）步骤，请参阅[1] ），并从l_one中删除项目（如果需要从ArrayList中删除，参见[1]），所以你得到O（N *（N + M））。
可以通过使用LinkedList为l_one降低复杂度为O（N * M）（由于从LinkedList去除是O（1），参见[2]），并且进一步 它低到O（N *日志（ M））通过使用TreeSet为l_two（因为在TreeSet中搜索需要O（log（M）），参见[3]）。
参考文献：
-
其他所有操作都以线性时间（
ArrayListjavadoc） -
所有操作的执行是可以预期的双向链表，（运行
LinkedListjavadoc） -
此实现为基本操作提供了有保证的log（n）时间成本（
add，remove和contains）（TreeSetjavadoc）
保证/指定Java收集方法的复杂性（以STL提供保证的方式）？我在Javadocs里找不到任何东西...... – 2010-10-24 22:19:15
@Oli：我添加了参考文献。 – axtavt 2010-10-24 22:29:40
哦，文档说明了这一点！谢谢，我看不到树木... – 2010-10-24 22:34:05
您使用了错误的收集你的目的..
既然你是用普通ArrayList做的复杂性会不会好，我不知道内部的实现，但我猜想它是二次的（因为它必须滚动两个列表），除非Java在内部将交集之前将两个列表转换为集合。
您应该Set接口（here）开始，并选择其收集更适合您的需求，我认为一个HashSet（恒定时间）或TreeSet（对数，但能保持自然顺序）将是最好的解决方案。
我想你要问的更重要的问题是retainAll（）函数的复杂性。假设没有哈希或快速查找，我会假设时间复杂度为O（n^2）。一个循环迭代列表和一个循环来比较每个项目。
Something告诉我这是一个面试问题;）我认为你应该开始考虑其他数据结构。如果你使用散列，这个问题可能是O（n） – 2010-10-24 22:10:24
简言之：
ArrayList.add()是O(1)。ArrayList.retainAll(other)是O(N1 * N2)其中N1是this和N2尺寸的other大小。 （实际成本取决于保留，以除去元素的元素比。）iter.hasNext()和iter.next()是O(1)用于ArrayList迭代器。
这一切都是你所期望的基础上，精神上建模一个ArrayList作为Java数组。
您可以使用LinkedHashSet在保留订单的同时获取Set的性能。注意：您只需要在第一个集合中保留订单，第二个订单的顺序并不重要？你需要保持重复吗？如果是这样，第一个集合必须是一个列表，但第二个集合仍然可以是一个集合。 – 2010-10-24 23:44:23