设置操作的复杂性 [英] Complexity of Set operations

问题描述

这就是我正在做的事情：

字符串一=某些字符串

字符串二=某些字符串

This is what I am doing:
String one = "some string"
String two = "some string"

我想知道字符串一个和两个中的所有字符，它们应该按顺序出现，因为它们在字符串一中

I want to know all the characters that are in string one and two and they should come in order as they are in string one

我写了一个Java程序，通过使用Collections对两个集合执行集合操作。

我想知道执行集合操作的复杂性是什么？多项式时间或线性时间

I wrote a Java program which by using Collections performs set operations on both the collection.
What I would like to know that what is the complexity of performing set operations, is it polynomial time or linear time

我的程序在这里

/*
 * 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（）。

Its complexity is O(N * (N + M)), where 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））。

It works in the following way: for each character of l_one (there are N of them) it scans l_two (since l_two is an ArrayList, scan is linear, so it takes O(M) steps, see [1]) and removes item from l_one if necessary (removing from ArrayList takes O(N), see [1]), so you get O(N * (N + M)).

您可以将复杂度降低为O（N N * M），将 LinkedList 用于 l_one （因为从 LinkedList 为O（1），请参见[2]），然后通过使用 TreeSet 将
进一步降低为O（N * log（M））。 l_two （因为在 TreeSet 中进行搜索需要O（log（M）），请参见[3]）。

You can lower the complexity to O(N * M) by using LinkedList for l_one (since removing from LinkedList is O(1), see [2]), and further lower it to O(N * log(M)) by using TreeSet for l_two (since searching in TreeSet takes O(log(M)), see [3]).

参考文献：

1. 所有其他操作以线性时间运行（ ArrayList javadoc ）
   
2. 所有操作均按双向链接列表的预期执行，（ LinkedList javadoc ）


3. 此实现为基本操作提供了保证的log（n）时间成本（添加，删除和包含）（ TreeSet javadoc ）

1. All of the other operations run in linear time (ArrayList javadoc)
2. All of the operations perform as could be expected for a doubly-linked list, (LinkedList javadoc)
3. This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains) (TreeSet javadoc)

这篇关于设置操作的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！