Сложность операций Set - PullRequest
Новая
       18

Сложность операций Set

2 голосов
/ 25 октября 2010

Вот что я делаю:
String one = "некоторая строка"
Строка два = "какая-то строка"

Я хочу знать все символы в строке один и два , и они должны располагаться по порядку, как в строке один

Я написал программу на 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

Ответы [ 4 ]

5 голосов
/ 25 октября 2010

Его сложность составляет 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)).

Вы можете снизить сложность до O (N * M), используя LinkedList для l_one (поскольку удаление из LinkedList - это O (1), см. [2]), а такжеуменьшите его до O (N * log (M)), используя TreeSet для l_two (поскольку поиск в TreeSet требует O (log (M)), см. [3]).

Ссылки:

  1. Все остальные операции выполняются за линейное время (ArrayList javadoc )
  2. Все операции выполняются, как и следовало ожидать для двусвязного списка , (LinkedList javadoc )
  3. Эта реализация обеспечивает гарантированный журнал (n)временные затраты на основные операции (add, remove и contains) (TreeSet javadoc )
4 голосов
/ 25 октября 2010

Я думаю, что более важный вопрос, который вы пытаетесь задать, заключается в сложности функции retainAll ().Предполагая, что нет хэшей или быстрого поиска, я бы предположил, что сложность времени равна O (n ^ 2).Один цикл для итерации списка и один цикл для сравнения каждого элемента.

1 голос
/ 25 октября 2010

Вы используете неправильную коллекцию для своих целей ..

Поскольку вы делаете это с простым ArrayList, сложность не будет хорошей, я не знаю внутреннюю реализацию, но я предполагаю, что она квадратична (так как она должна прокручивать оба списка), если только Java не преобразует внутренне два списка для наборов перед пересечением.

Вы должны начать с интерфейса Set ( здесь ) и выбрать, какая коллекция больше подходит для ваших нужд, я думаю, что HashSet (постоянное время) или TreeSet (логарифмическая, но в состоянии сохранить естественный порядок) будет лучшим решением.

0 голосов
/ 25 октября 2010

Кратко:

  • ArrayList.add() равно O(1).

  • ArrayList.retainAll(other) равно O(N1 * N2), где N1 обозначаетразмер this и N2 - это размер other.(Фактическая стоимость зависит от соотношения оставшихся элементов к удаленным элементам.)

  • iter.hasNext() и iter.next() равны O(1) для ArrayList итератора.

Это все, как и следовало ожидать, основанное на мысленном моделировании ArrayList как массива Java.

...