VPF::Поиск в неупорядоченном массиве со сложностью N/3

phpsuxxx

Дата 11.8.2014, 11:47 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 6.8.2014

Репутация: нет
Всего: нет

Почему если случайно выбирать номер элемента, время поиска существенно уменьшается?

Код


//Так в среднем 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;
 }

Это сообщение отредактировал(а) phpsuxxx - 11.8.2014, 14:20

Akina

Дата 11.8.2014, 12:13 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

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

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

volatile

Дата 11.8.2014, 13:57 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 2
Всего: 85

Цитата(phpsuxxx @ 11.8.2014, 11:47

)

если случайно выбирать номер элемента, время поиска существенно уменьшается?

кто вам это сказал ?

Это сообщение отредактировал(а) volatile - 11.8.2014, 14:01

phpsuxxx

Дата 11.8.2014, 14:13 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 6.8.2014

Репутация: нет
Всего: нет

Цитата(volatile @ 11.8.2014, 13:57)

кто вам это сказал ?

Прочитал в одной книге. Написал программу - работает действительно быстрее.

volatile

Дата 11.8.2014, 14:18 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 2
Всего: 85

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;
}

до последнего ретурна здесь вообще никогда не дойдет, так что если в массиве нет искомого числа, цикл будет вычным
(но это так, чтоб не пугались, если зависнет smile

)

phpsuxxx

Дата 11.8.2014, 14:23 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 6.8.2014

Репутация: нет
Всего: нет

Цитата(volatile @ 11.8.2014, 14:18)

Цитата(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.
А насчёт зависания в книге сказано, что этот алгоритм для случаев когда нужный элемент заведомо есть в массиве.
Кстати, поправил ошибку в коде, сейчас можно собрать программу и убедиться самим.

Это сообщение отредактировал(а) phpsuxxx - 11.8.2014, 14:27

Akina

Дата 11.8.2014, 19:03 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Цитата(phpsuxxx @ 11.8.2014, 15:23

)

По видимому n/e как написал Akina.

Не точно, но близко. Счётная задачка, вполне на уровне 9 или 10 класса.
Причём чем больше n, тем ближе знаменатель к е. А это уже 1 курс технического ВУЗа.

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »