Поиск в массиве менее чем за время O (n)

У меня есть массив, где каждый элемент либо меньше, либо больше, чем предыдущий элемент \ $ \ {x_i = x_ {i-1} \ pm 1 \} \ $. Я хочу найти элемент в нем меньше, чем \ $ O (n) \ $ time. Я реализовал его следующим образом:

public int searchArray(int[] arr, int i, int elem) {

    if (i > arr.length - 1 || i < 0) {
        return -1;
    }

    if (arr[i] == elem) {
            return i;

    } else {
            int diff = Math.abs(elem - arr[i]);
            int index = searchArray(arr, i + diff, elem);
            if (index == -1) {
                index = searchArray(arr, i - diff, elem);
                if (index == -1) {
                    return -1;
                }
            }
            return index;
    }
}

И назовем это так:

int[] arr = {2, 1, 2, 3, 4, 3, 2, 3, 4, 5, 6, 5, 4, 3, 4};
int index = searchArray(arr, 0, 3);

Он отлично работает, но может ли он быть улучшен? В частности, есть ли способ сделать это итеративно? И текущий алгоритм меньше, чем \ $ O (n) \ $. Я думаю, это так, но я не уверен.

47 голосов | спросил user3011937 3 TueEurope/Moscow2013-12-03T09:18:49+04:00Europe/Moscow12bEurope/MoscowTue, 03 Dec 2013 09:18:49 +0400 2013, 09:18:49

12 ответов


56

В то время как другие ответы дают хорошие моменты, мне нужно задаться вопросом, почему вы используете рекурсию. Это такая простая проблема для решения с помощью цикла for.

Я предполагаю, что вы не должны начинать с любого индекса, кроме индекса 0, поэтому рассмотрите следующую процедуру:

public int searchArray(int[] arr, int elem) {

    for (int i = 0; i < arr.length; ) {
        if (arr[i] == elem) {
            return i;
        }
        i += Math.abs(elem - arr[i]);
    }
    return -1;
}

(Если вам нужно запустить поиск частично через массив, вы можете снова добавить параметр ввода offset и запустить i).

Суть в том, что рекурсия переполнена, эта система - \ $ O (n) \ $, но стоимость каждого цикла меньше, чем одно и то же, используя рекурсию.

Я не знаю, как решить данную проблему с помощью системы лучше, чем \ $ O (n) \ $ сложность.


Обсуждение сложности - почему это \ $ O (n) \ $

Этот ответ породил много дискуссий о сложности, что этот метод только когда-либо сканирует, в лучшем случае, половину членов входного массива и, следовательно, он должен быть сложным \ $ O \ left (\ frac {n} { 2} \ right) \ $ вместо \ $ O (n) \ $. Аргумент приведен в следующем виде:

  

Рассмотрим наихудшие данные 1,2,1,2,1,2,1,2,1,2,1,2 и поисковый термин 3. Для этой ситуации метод начнется с data[0], а затем перейдите к data[2], затем data[4] и скоро. Он никогда не будет проверять данные data[1] и другие нечетные индексы. Если поисковый запрос еще больше «отличается» от фактических данных (например, 100), тогда метод будет выполнять только одно сравнение в data[0] и затем вернет ' не найден '-1.

Это интересное замечание, что только когда-либо нужно сканировать половину данных не более . Это особенно интересно, учитывая «наивный» метод, который просто сканирует данные по одному члену и возвращает и возвращает, когда он находит значение. Этот «наивный» метод, безусловно, имеет \ $ O \ left (n \ right) \ $ 'производительность' и сложность, а «skip-method» будет более чем в два раза быстрее.

Важно отметить, что алгоритмы масштабируют относительно количества данных , а не относительно друг друга!

Итак, рассмотрим гипотетический набор наихудших данных 1,2,1,2,1,2,.... и поисковый термин 3 , Эта гипотеза, по-видимому, выполняется поиском в 4 миллисекундах методом пропуска, а в 8 миллисекунд наивным методом. Теперь мы удваиваем количество данных, что происходит? Время обработки для обоих методов удваивается!

В обоих случаях производительность алгоритмов удваивается для каждого удвоения объема данных. Именно это делает оба алгоритма \ $ O (n) \ $ сложность. Из Википедии :

  

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

Перевернув аргумент, предположив, что skip-метод имеет \ $ O \ left (\ frac {n} {2} \ right) \ $ complex, я ожидал бы, что если я удвою данные, время выполнения увеличится лишь на половину, или на 50%. Это «очевидно» неверно для метода пропуска (или наивного метода).

Оба метода имеют сложность \ $ O (n) \ $, потому что оба они одинаково масштабируются с увеличением объема данных.

Но только потому, что они масштабируются одинаково, не означает, что один метод не лучше другого ... очевидно .

ответил rolfl 3 TueEurope/Moscow2013-12-03T15:35:03+04:00Europe/Moscow12bEurope/MoscowTue, 03 Dec 2013 15:35:03 +0400 2013, 15:35:03
32

Проблема в \ $ O (n) \ $. Рассмотрим случай, описанный в 200_success.

У вас есть последовательность чередующихся 1 и 2, где один 1 заменяется на 3.

Когда вас попросят найти 3, вы знаете, после проверки первого элемента, что он будет иметь индекс. Но если каждый нечетный индекс содержит a 2, то любой четный индекс может содержать 3, поэтому вы не можете гарантировать, что 3 не находится в последнем индексе, который вы ищете. Это означает, что вам придется искать в \ $ O (\ dfrac {n} {2}) \ $ местах. \ $ O (\ dfrac {n} {2}) \ $ = \ $ O (n) \ $, поэтому проблема равна \ $ O (n) \ $.

Нет правильного алгоритма, который может иметь лучшую производительность в худшем времени, чем это.

Более интересный вопрос - это то, что происходит, если вы знаете, что число не больше, чем какая-либо фиксированная верхняя граница.

ответил Taemyr 3 TueEurope/Moscow2013-12-03T14:04:56+04:00Europe/Moscow12bEurope/MoscowTue, 03 Dec 2013 14:04:56 +0400 2013, 14:04:56
14

Вам не нужно оглядываться назад, если вы начинаете с 0.

Доказательство по индукции по шагам алгоритма j:

При j = 0, i (j) = 0, вы не можете вернуться назад.

Для j> 1, есть два случая: первый, мы нашли наш номер. Во-вторых, существует разница diff(j) = abs(elem - array[i(j)]). Тогда число в массиве array[i(j),i(j)+diff) не может содержать элемен. По индуктивному предположению ни один элемент в массиве array[i(j-1),i(j)=i(j-1)+diff(j-1)) также содержит это число. Итак, следующим возможным индексом для i является i(j)+diff(j) (= i(j+1))

Но этот алгоритм действительно находится в O (n), как уже ответил Taemyr.

ответил kutschkem 3 TueEurope/Moscow2013-12-03T14:28:57+04:00Europe/Moscow12bEurope/MoscowTue, 03 Dec 2013 14:28:57 +0400 2013, 14:28:57
12

Вот несколько общих советов:

  • Избегайте однобуквенных имен параметров. Для небольших циклов i все в порядке, но оно не должно протекать в сигнатурах методов - особенно, когда index - всего четыре буквы.

  • Согласоваться с if-else. У вас есть два блока if, которые оба возвращаются из метода , либо используйте else для обоих, либо ни того, ни другого. В противном случае появляется быстрый взгляд, что он не выходит.

    if (x)
        return foo;
    else if (y)
        return bar;
    else
        baz
    

    или

    if (x)
        return foo;
    if (y)
        return bar;
    baz
    
  • if (index == -1) return -1; является избыточным, поскольку за ним сразу следует индекс возврата return index;.

  • Math.abs не требуется, поскольку вы сначала добавляете, а затем вычитаете diff. Порядок здесь не имеет значения.

  • Я бы отменил параметры i и elem и добавил перегруженную форму, которая опускает i, и просто вызывает другую с i = 0. Это обеспечивает более удобный API для абонентов. Трехпараметрическая версия также может быть приватной классу, содержащему оба, если только внешняя форма необходима извне.

Что касается вашего вопроса о временной сложности, моя кишка говорит, что, возможно, в худшем случае может возникнуть бесконечный цикл, но я еще не слишком глубоко вникал в настоящий алгоритм.

Чтобы переписать это итеративно, вам нужно будет использовать стек, чтобы разрешить обратное отслеживание, поскольку вам иногда приходится разворачивать оба направления. Вот быстрый удар по нему в psuedocode:

i = 0
ответил David Harkness 3 TueEurope/Moscow2013-12-03T09:58:23+04:00Europe/Moscow12bEurope/MoscowTue, 03 Dec 2013 09:58:23 +0400 2013, 09:58:23
9

Это можно сделать в O (1) раз, если нормально использовать O (n) время для создания таблицы соответствия только один раз. Если массив останется прежним, и вы будете искать несколько раз, это может быть хорошим подходом. Следующий псевдокод предполагает, что вы собираетесь искать весь массив (из индекса 0) и возвращает первый индекс, в котором находится элемент. Его можно легко модифицировать для поиска по индексу> 0, а также рассказать вам все индексы, в которых происходит элемент.

Скажем, ваш входной массив называется arr, длина arr - n, а arr [0] - k. Мы знаем, что значения в arr находятся в диапазоне [k-n + 1, k + n-1], всего 2n-1 разных значений. Для каждого возможного целого в диапазоне, мы делаем запись для него в нашей таблице поиска:

// Initialization
for i = 0 to 2n-2 
    lookup[i] = -1

k = arr[0]

// Build lookup-table
for i = 0 to n-1
    index = arr[i]-k+n-1
    if lookup[index] == -1
        lookup[index] = i // We only store the position in arr of the first occurrence


// Search for, say, s (assuming s is in the valid range, no check for it here)
lookup[s-k+n-1] // A result >= 0 is a hit, giving the (first) position of s in arr
ответил Tore 4 WedEurope/Moscow2013-12-04T12:18:44+04:00Europe/Moscow12bEurope/MoscowWed, 04 Dec 2013 12:18:44 +0400 2013, 12:18:44
6
public static int search(int[] array, int start, int end, int target)
{

    if(array[start] == target)return start;
    if(array[end] == target)return end;
    if(Math.abs(array[start]-target) + Math.abs(array[end]-target) >= end-start+1)
        return -1;


    int middle = (start+end) / 2;

    int val = search(array, start, middle, target);
    if(val != -1)return val;

    val = search(array, middle+1, end, target);
    if(val != -1)return val;

    return -1;
}

Вот что я придумал. Он фактически разбивает список посередине. После каждого разделения он проверяет, возможно ли, чтобы цель была в этом массиве. Math.abs(array[start]-target) + Math.abs(array[end]-target) >= end-start+1 охватывает это (он использует тот факт, что вам нужно получить от первого номера до цели, затем обратно вниз до последнего числа в массиве). Если это возможно, мы продолжаем разделение на это, пока цель не станет началом или концом диапазона.

Для примера того, как это сокращается, рассмотрим массив, начинающийся и заканчивающийся в 1, и это всего лишь длина 5. Вас попросят найти 4 в нем. Вы знаете, что это невозможно, так как вам нужно потратить 3 слота на 4, а затем 3 - на один. Это означает, что длина должна быть не менее 7. Таким образом, мы можем немедленно вернуть -1.

Это действительно даже немного помогает в случае 12121212121212 ..... 321212, потому что вы часто получаете подсписок 121, который не может иметь 3.

Это сказано. Он по-прежнему выглядит O (n) в худшем случае для меня. Хотя я не удивлюсь, если у этого есть сублинейный средний случай.

ответил Cruncher 3 TueEurope/Moscow2013-12-03T19:56:07+04:00Europe/Moscow12bEurope/MoscowTue, 03 Dec 2013 19:56:07 +0400 2013, 19:56:07
5

Функция должна быть

public static int searchArray(int[] array, int value) {
    // Call private static int searchArray(int[] array, int index, int value)
    return searchArray(array, 0, value);
}

â € |, потому что, если вызывающий может выбрать любой начальный индекс, результат может быть неправильным. (Рассмотрим searchArray(arr, 12, 6) в вашем примере.) Эти функции должны быть static, поскольку они не зависят от переменных экземпляра.

Я считаю, что наихудший случай был бы как минимум O ( n ), как в следующем примере:

int[] arr = {1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 3};
int index = searchArray(arr, 0, 3);
ответил 200_success 3 TueEurope/Moscow2013-12-03T11:08:34+04:00Europe/Moscow12bEurope/MoscowTue, 03 Dec 2013 11:08:34 +0400 2013, 11:08:34
2

Здесь есть много хороших ответов, но я чувствовал, что хотел взять удар по этому вопросу.

Если ваша задача состоит в поиске массива с \ $ O (n) \ $ или меньше сложностью , я наиболее самодовольно предлагаю:

int search(int[] data, int value) {
    for (int i = 0 ; i < data.length ; i++) {
        if (data[i] == value) {
            return i;
        }
    }
    return -1;
}

Поэтому я сомневаюсь, что это так; либо исходный искатель неправильно использовал big \ $ O \ $ для ссылки на время выполнения , или вы действительно слишком усложняете поиск.

Предполагая, что они означают время выполнения \ $ R <k * N \ $ мое решение ниже отличается от вашего в двух важных аспектах:

Похоже, вы понимаете, что можете сэкономить время, пропустив вперед, используя тот факт, что для двух значений \ $ x \ $ и \ $ y \ $ в индексах \ $ i \ $ и \ $ j \ $ соответственно, где \ $ i <j \ $, \ $ y \ le x + j - i \ $ и \ $ y \ ge x + i - j \ $. Тем не менее, ваш алгоритм идет вперед и ищет назад, когда он проскакивает вперед; это не обязательно. Вы можете пропустить вперед, потому что значение поиска не может находиться в диапазоне, который вы пропустили .

Рекурсия не рекомендуется, так как она расширяет требования к хранению для алгоритма, занимая стек, затрудняет оценку сложности сложности алгоритма и обычно увеличивает \ $ k \ $. Это вполне возможно для поиска с циклом, который легко показать как \ $ O (n) \ $ time и \ $ O (k) \ $ space complex .

int searchWeirdlyOrganizedArray(int[] data, int forValue) {
    int i = 0;
    while (i < data.length) {
        if (data[i] == forValue) {
            return i;
        } else {
            i += abs(forValue - data[i]);
        }
    }
    return -1;
}

Заключительное примечание: я ошибся в своем комментарии, что поиск \ $ \ lbrace1, 2, 1, 2, \ dots \ rbrace \ $ для 3 потребует сравнения \ $ N \ $. Он требует \ $ \ frac {N} {2} \ $ сравнения, потому что все 2s пропускаются. Если значения 2s и 1s меняются на противоположные (\ $ \ lbrace2, 1, 2, 1, \ dots \ rbrace \ $), то это сравнение \ $ 1 + \ frac {N - 1} {2} \ $, как только начальное сравнение продвигает поиск на 1, но после этого каждые 2 пропускается. Тем не менее, я был прав, что это еще \ $ O (n) \ $ сложность .

ответил sqykly 24 TueEurope/Moscow2013-12-24T06:06:51+04:00Europe/Moscow12bEurope/MoscowTue, 24 Dec 2013 06:06:51 +0400 2013, 06:06:51
0

Я не думаю, что вы найдете лучший худший случай, чем \ $ O (n) \ $. Но если вы хотите сделать много запросов в одном массиве (т. Е. Проверить несколько номеров в одном массиве), вы можете использовать подсчет сортировки .

Здесь можно сделать одно улучшение, которое работает в препроцессе \ $ O (n) \ $ и \ $ O (1) \ $ время для каждого запроса. То есть вы можете делать \ $ t \ $ запросы в \ $ O (t + n) \ $ time, а не в \ $ O (nt) \ $, как вам нужно было бы делать с вашим текущим методом.

Один очевидный способ - отсортировать массив в \ $ O (nlogn) \ $ и выполнить двоичный поиск в \ $ O (logn) \ $. Для запросов \ $ t \ $ время будет \ $ O (tlogn + nlogn) \ $. Но это все еще можно улучшить.

Вы можете сортировать свои числа в \ $ O (n) \ $ время, используя сортировку counting, но есть один компромисс таким образом. То есть, если наибольшее количество в массиве - \ $ k \ $, то вам понадобится массив размера \ $ k \ $ в вашей ОЗУ, что может вызвать проблемы в редких случаях.

Этот код работает только для неотрицательных целых чисел. С небольшим изменением алгоритм будет работать и для отрицательных целых чисел.

ответил FazeL 5 42015vEurope/Moscow11bEurope/MoscowThu, 05 Nov 2015 09:39:12 +0300 2015, 09:39:12
0

Вот другое решение:

public static void radixSort(int[] data) {
    boolean flag = true;
    int divisor = 1;
    Queue [ ] buckets = new Queue[10];
    for (int i = 0; i < 10; i++)
            buckets[i] = new LinkedList();

    while (flag) {
            flag = false;
            // first copy the values into buckets
            for (int i = 0; i < data.length; i++) {
                    int hashIndex = (data[i] / divisor) % 10;
                    if (hashIndex > 0) flag = true;
                    buckets[hashIndex].add(data[i]);
            }
                    // then copy the values back into vector
            divisor *= 10;
            int i = 0;
            for (int j = 0; j < 10; j++) {
                    while (! buckets[j].isEmpty()) {
                            Integer ival = (Integer) buckets[j].element();
                            buckets[j].remove();
                            data[i++] = ival.intValue();
                    }
            }
    }
}

public static int searchArray(int[] arr,int offset,int elm) {
    radixSort(arr);
    return Arrays.binarySearch(arr, elm);
}

Первая часть, radixSort, is \ $ O (kn) \ $, а вторая часть, binarySearch, is \ $ O (log (n)) \ $. В качестве альтернативы написанию radixSort вы могли бы использовать стандартный Java Arrays.sort, который имеет порядок \ $ O (n log (n)) \ $, поскольку это реализация быстрого сортировки.

Это было мое старое решение, которое, как указывалось, все еще \ $ O (n) \ $:

Решение довольно просто. Вы можете оптимизировать это до \ $ O (\ frac {n} {2}) \ $, потому что, когда вы смотрите на значение элемента, вы знаете, что значение элемента до и после этого элемента.

Простая функция:

public int searchArray(int[] arr,int offset,int elm) {          
     if(arr != null && arr.length > (offset+1)) {
            for(int i = (offset+1); i < arr.length; i+=2) {                
                int absVal = Math.abs(elm - arr[i]);
                if(absVal == 1) {
                    int behind = i - 1;
                    int infront = i + 1;
                    if(arr[behind] == elm) {
                        return behind;
                    } else if(arr[infront] == elm) {
                        return infront;
                    }
                } else if(absVal == 0) {
                    //we are the value
                    return i;
                }
            }
        } else if(arr != null && arr.length > offset && arr[offset] == elm) {
            return offset;
        }                    
        return -1;              
    }

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

Код полного кода:

package cstura;

import javax.xml.ws.Holder;

/**
 *
 * @author cstura
 */
public class Test {

    public static void main(String[] args) throws Throwable {
        int[] arr = {2, 1, 2, 3, 4, 3, 2, 3, 4, 5, 6, 5, 4, 3, 4};        
        for(int i = 0; i < arr.length; ++i) {
            Holder<Integer> numItrs = new Holder(0);
            int idx = searchArray(arr,0,arr[i],numItrs);
            System.out.println(String.format("first position of %d in the array is: %d total itrs were: %d",arr[i],idx,numItrs.value));
        }
    }

    public static int searchArray(int[] arr,int offset,int elm,Holder<Integer> numItrs) {
        int itrs = 0;
        try {            
            if(arr != null && arr.length > (offset+1)) {
                for(int i = (offset+1); i < arr.length; i+=2) {                
                    itrs++;
                    int absVal = Math.abs(elm - arr[i]);
                    if(absVal == 1) {
                        //the value if infront or behind us (maybe)
                        int behind = i - 1;
                        int infront = i + 1;
                        if(arr[behind] == elm) {
                            return behind;
                        } else if(arr[infront] == elm) { //if it's not behind then it must be infront.
                            return infront;
                        }
                    } else if(absVal == 0) {
                        //we are the value
                        return i;
                    }
                }
            } else if(arr != null && arr.length > offset && arr[offset] == elm) {
                return offset;
            }

            return -1;  
        }finally {
            numItrs.value = itrs;
        }
    }        
}
ответил cstura 4 WedEurope/Moscow2013-12-04T14:02:56+04:00Europe/Moscow12bEurope/MoscowWed, 04 Dec 2013 14:02:56 +0400 2013, 14:02:56
-3

Есть ли ограничение, указывающее, что массив должен (или не может быть) в определенном порядке? Если вы сохраните отсортированный массив, вы можете выполнить двоичный поиск, который будет выполняться в O (log (n)). Рекурсивная и итеративная реализация. Конечно, недостаток состоит в том, что массив нужно сортировать, но pro это то, что вы можете искать миллионы записей менее чем за 10 итераций /рекурсий.

Из статьи Википедии о алгоритме бинарного поиска:

int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin)
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = midpoint(imin, imax);

      // three-way comparison
      if (A[imid] > key)
        // key is in lower subset
        return binary_search(A, key, imin, imid-1);
      else if (A[imid] < key)
        // key is in upper subset
        return binary_search(A, key, imid+1, imax);
      else
        // key has been found
        return imid;
    }
}
ответил NeoZeroX21 3 TueEurope/Moscow2013-12-03T19:49:25+04:00Europe/Moscow12bEurope/MoscowTue, 03 Dec 2013 19:49:25 +0400 2013, 19:49:25
-3

Я уверен, что есть алгоритмы, которые в среднем лучше, чем \ $ O (n) \ $ в среднем.

Например, если алгоритм поиска ищет массив source, длина length, индексирование с помощью индекса index для поиска target, то если source[index] != target, то следующее значение для index может быть index + abs(source[index]-target), который может пропускать многие элементы или даже запускать конец массива и завершать.

То есть вам нужно всего лишь проверить несколько элементов массива, поскольку их значения ограничены.

Лучший математик, чем я, сможет рассказать вам, что такое верхняя граница, но я предполагал бы, что \ $ O (1) \ $.

ответил quamrana 4 WedEurope/Moscow2013-12-04T13:50:33+04:00Europe/Moscow12bEurope/MoscowWed, 04 Dec 2013 13:50:33 +0400 2013, 13:50:33

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132