Большой О двух функций - PullRequest
Новая
       21

Большой О двух функций

1 голос
/ 29 ноября 2011

Я давно занимаюсь программированием на PHP, и, поскольку я не являюсь специалистом по информатике / математике, у меня есть только базовое понимание нотации Big O, поэтому я взял функцию и попробовал улучшить его и выразить их обоих в Big O:

Пример 1 

function foo($j) {
    $ids = array();
    while (count($ids) < $j) {
        $id = gen_id();  // assume this function will return you an integer
        if (!in_array($id, $ids)) {
            $ids[] = $id;
        }
    }
    return $ids;
}

Я бы улучшил эту функцию, удалив цикл while для count($ids) и заменив его на for, так что count($ids) не нужно оценивать каждый раз в цикле, а также заменив is_array на isset и переместить значения в клавиши (isse t быстрее, чем in_array)

Пример 2 - Улучшено 

function foo($j) {
    $ids = array();
    for($i = 1; $i<= $j; ++$j) {
        $id = gen_id();  // assume this function will return you an integer
        if (!isset($ids[$id])) {
            $ids[$id] = true;
        }
        else {
            --$i;
        }
    }
    return $ids;
}

Я бы выразил вышеперечисленные функции в следующих обозначениях Big O:

Пример 1: O (n ^ 2), Пример 2: O (n)

Я прав в своих примечаниях? Есть ли лучший способ сделать ту же функцию?

Заранее спасибо!

Ответы [ 4 ]

1 голос
/ 09 мая 2012 
for ($i=0;$i<$j; ) {
  $id = gen_id();
  if (!isset($ids[$id])) {
    $ids[$id]=true;
    $i++;
  }
}
1 голос
/ 29 ноября 2011

Вот как я бы написал эту функцию в более простом подходе: внутренний цикл for является идеальным сценарием для цикла do ... while. 

function foo( $j)
{
    $ids = array();
    for( $i = 0; $i < $j; $i++)
    {
        do
        {
            $id = gen_id();
        } while( isset( $ids[$id]));
        $ids[$id] = true;
    }
    return $ids;
}

Редактировать: На самом деле, эта функция O($j) / O(n), так как gen_id() и isset() оба постоянны O(1) (isset() - это поиск в хеш-таблице).Таким образом, внутренняя эффективность цикла for равна постоянному времени O(1), что делает всю функцию O(n).

1 голос
/ 29 ноября 2011

Ваше мышление хорошее, но вы не правы.

Следующее прояснит вас .... 

function foo($j) 
{
 for($i=1;$i<j;$i++)
 {
  // some code here
 }
 for($i=1;$i<j;$i++)
 {
 // some code here
 }
}

Вы можете подумать, что это будет 0 (2n), но постоянный член не выражается в нотации 0 Так Сложность 0 (n).

Смотрите следующее 

 function foo($j) 
{
 for($i=1;$i<j;$i++)
 {
    for($k=1;$k<i;$k++)
    {
     // some code here
    }
 }

}

Имеет сложность 0 (n ^ 2).

1 голос
/ 29 ноября 2011

Прежде всего: постоянные коэффициенты не имеют значения в обозначении Big O, что означает O(n) = O(cn) для любой постоянной c != 0.

Для первого я знаю, count($ids) занимает O(1) время для оценки, но как насчет in_array($id, $ids)?Я точно не знаюНо если это O(n) или O(logn), тогда целое будет O(n^2) или O(nlogn).Я не думаю, что это может быть реализовано за O(1) время, что может дать O(n) время для всей функции.

Для 2-го это O(n) и, по-видимому, быстрее, чем 1-гоодин.

РЕДАКТИРОВАТЬ: Я просто думаю, что Википедия описала большой O нотации как-то ясно.Иди и прочитай немного.

...