Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Поиск в неупорядоченном массиве со сложностью N/3

Автор: phpsuxxx 11.8.2014, 11:47

Почему если случайно выбирать номер элемента, время поиска существенно уменьшается? Код //Так в среднем n/2 int LineSearch(int A[], int n, int key)  {       for (int i=0; i<n; i++)              if (A[i]==key) return i;       return -1;  } Код //А так в среднем n/3 int Search(int A[], int n, int key)  {       int i=0;       while(true)       {             if (A[rand()%n]==key) return i;             ++i;       }       return -1;  }

Автор: Akina 11.8.2014, 12:13

Среднее время поиска... и не n/3, а n/e.

Автор: volatile 11.8.2014, 13:57

Цитата(phpsuxxx @  11.8.2014,  11:47 ) если случайно выбирать номер элемента, время поиска существенно уменьшается? кто вам это сказал ?

Автор: phpsuxxx 11.8.2014, 14:13

Цитата(volatile @ 11.8.2014,  13:57) кто вам это сказал ? Прочитал в одной книге. Написал программу - работает действительно быстрее.

Автор: volatile 11.8.2014, 14:18

phpsuxxx,  В том варианте что у вас, оно работать в среднем не будет быстрее Даже несколько дольше. Проведите несколько сотен экспериментов, с разными случайными числами не забудьде сделать srand от текущео времени и вы убедитетесь Добавлено через 2 минуты и 10 секунд зы Цитата(phpsuxxx @  11.8.2014,  11:47 ) int Search(int A[], int n, int key)  {       while(true)             if (A[rand()%n]==key) return i;       return -1;  } до последнего ретурна здесь вообще никогда не дойдет, так что если в массиве нет искомого числа, цикл будет вычным (но это так, чтоб не пугались, если зависнет   )

Автор: phpsuxxx 11.8.2014, 14:23

Цитата(volatile @ 11.8.2014,  14:18) phpsuxxx,  В том варианте что у вас, оно работать в среднем не будет быстрее Даже несколько дольше. Проведите несколько сотен экспериментов, с разными случайными числами не забудьде сделать srand от текущео времени и вы убедитетесь Добавлено @ 14:20 зы Цитата(phpsuxxx @  11.8.2014,  11:47 ) int Search(int A[], int n, int key)  {       int i=0;       while(true)       {             if (A[rand()%n]==key) return i;             ++i;       }       return -1;  } до последнего ретурна здесь вообще никогда не дойдет, так что если в массиве нет искомого числа, цикл будет вычным (но это так, чтоб не пугались, если зависнет   ) Запустил цикл на тысячу раз. В среднем чуть больше n/3. По видимому n/e как написал Akina. А насчёт зависания в книге сказано, что этот алгоритм для случаев когда нужный элемент заведомо есть в массиве. Кстати, поправил ошибку в коде, сейчас можно собрать программу и убедиться самим.

Автор: Akina 11.8.2014, 19:03

Цитата(phpsuxxx @  11.8.2014,  15:23 ) По видимому n/e как написал Akina. Не точно, но близко. Счётная задачка, вполне на уровне 9 или 10 класса. Причём чем больше n, тем ближе знаменатель к е. А это уже 1 курс технического ВУЗа.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)