Big-O нотация, как работать через него php или javascript - PullRequest
Новая
       17

Big-O нотация, как работать через него php или javascript

0 голосов
/ 28 марта 2012

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

Мне сказали, что если я возьму массив отсортированных значений INT, как я напишу функцию, которая по существу вернет true (или false), если сумма любых двух чисел в массиве равна нулю. Поэтому я предполагаю, что у меня будет такой массив. 

array("0","1","2","3","4")

Просто пример. Я уверен, что массив намного больше. Что я пытаюсь понять, как я могу это сделать? Я не хочу перебирать массив x раз, где x - это счетчик массива, а затем некоторые, чтобы попробовать каждую комбинацию, это просто безумие, и если массив достаточно большой, все, что я делаю, - это исчерпание памяти и горлышко бутылки Я сам на стороне сервера или на стороне клиента, в зависимости от того, какой маршрут я использую, с помощью JavaScript или PHP

Итак, каков хороший способ решения этой проблемы, потому что я точно не имею приличной подсказки на данный момент.

Ответы [ 2 ]

3 голосов
/ 28 марта 2012

Обозначение Big O предназначено для классификации того, насколько «интенсивными» являются определенные алгоритмы.

Чтобы взять пример плохого алгоритма для решения этой проблемы, у вас есть n элементов массива и один способПосмотрите, есть ли для каждого элемента 1 любая комбинация сумм элементов с нулями, проверьте все остальные элементы n-1 на сумму нуля.

Big O игнорирует константы, поэтому "для каждого элемента" =n Вы проверяете n элементов и получаете O(n*n) или O(n^2).

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

Это должно помочь вам придумать алгоритм, который имеетболее низкая сложность, чем O(n^2).

0 голосов
/ 28 марта 2012

Поскольку оно отсортировано, вы можете найти значение, ближайшее к нулю, за время O (log (n)) с помощью двоичного поиска . Это значение разбивает массив на два подмассива, один со значениями меньше нуля (назовите его A ) и один со значениями больше нуля (назовите его B ). Очевидно, что два значения a и b суммируют до нуля тогда и только тогда, когда a = - b . Так что вы можете сделать: 

var i = 0;
var j = 0;
while (i < A.length && j < B.length) {
    if (A[i] == -B[j]) {
         return true;
    } else if (A[i] < -B[j]) {
        i++;
    } else {
        j++;
    }
}
return false;

Сложность алгоритма, описанного выше, составляет O (n / 2) = O (n), и, поскольку O (n)> O (log (n)) (бинарный поиск), общая сложность по-прежнему составляет O (n). ). Обратите внимание, что вы могли бы выполнить итерацию по массиву вместо использования бинарного поиска, и сложность была бы такой же.

Это на самом деле заставляет меня думать, что вы можете сделать все это за один цикл. Просто держите два указателя, один в начале массива, один в конце, и постепенно двигайтесь к середине. Сложность по-прежнему O (n / 2) = O (n): 

var i = myArray.length-1;
var j = 0;
while (i > j) {
    if (myArray[i] == -myArray[j]) {
         return true;
    } else if (myArray[i] > -myArray[j]) {
        i--;
    } else {
        j++;
    }
}
return false;
...