ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / SSS. Некоторые задачи
25 сообщений из 69, страница 2 из 3
  2  все
SSS. Некоторые задачи
    #39026296
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Какую? Свою? У меня щас идея - как заставить миллиард китайцев вместо Captcha решать
задачи области ИИ и краудсорсинга. И мне это во много раз интереснее чем академические
задачки. Мир сложнен и многообразен. Как можно изучая Скиенну изучать It? Никак.
It можно знать только приобщаясь к полезным стартапам и задачам нашего времени.
...
Рейтинг: 0 / 0
10.08.2015, 14:12
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39026600
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
mayton Как можно изучая Скиенну изучать It? Никак.

SashaMercury - можно можно
...
Рейтинг: 0 / 0
10.08.2015, 19:16
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39026708
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Интересно получается, для поиска минимума или максимума необходимо перебрать n элементов, а обновлять значение переменной в которой этот минимум хранится потребуется на порядок раз меньше. Например для 1.000.000.000.000 элементов потребуется в среднем 28 обновлений.
...
Рейтинг: 0 / 0
11.08.2015, 01:47
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39026709
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
SashaMercuryИнтересно получается, для поиска минимума или максимума необходимо перебрать n элементов, а обновлять значение переменной в которой этот минимум хранится потребуется на порядок раз меньше. Например для 1.000.000.000.000 элементов потребуется в среднем 28 обновлений.

Интересно в том контексте, что от этой избыточности(если это можно так назвать) было бы здорово избавиться.
...
Рейтинг: 0 / 0
11.08.2015, 02:18
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39026720
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TSashaMercuryТогда мне не нравится этот вариант. Какое-то 'грязное' решение. Неужели нет другого ?
Насколько я знаю нет ГСЧ без повторов, рано или поздно повторы будут. Так что другого нет.

Изобретай наиболее оптимальный способ отлова повторов:
1. Биткарта. Работает быстро, но при большом диапазоне займет много места.
2. Заполняешь, сортируешь, в один проход проверяешь на повторы, заменяя повторы на новые случайные, затем снова сортируешь, проверяешь и т.д. пока проверка не покажет что повторов нет. Лишнего места не займет, но будут затраты на сортировку.

Кстати, обладает ли такой алгоритм свойством конечность? Особенно при достаточно больших n и k ? Как долго он может выполняться ?


Судя по всему я нашёл решение данной задачи. Например алгоритм R

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
/*
  S has items to sample, R will contain the result
*/
ReservoirSample(S[1..n], R[1..k])
  // fill the reservoir array
  for i = 1 to k 
      R[i] := S[i] 

  // replace elements with gradually decreasing probability
  for i = k+1 to n 
    j := random(1, i)   //  important: inclusive range
    if j <= k
        R[j] := S[i]



Добавлю свой перевод обоснования из w.
Согласно алгоритму первоначально необходимо заполнить целевой массив R мощностью k первыми k элементами множества S. Следом необходимо перебрать оставшиеся в S элементы, до тех пор пока они не закончатся. На каждой итерации последнего перебора для каждого элемента s[i] алгоритм генерирует случайное число j из диапазона [1,i]. Если j<=k, то происходит присваивание r[j]<-s[i]. В действительности, на каждой итерации вероятность того, что будет выбран элемент для целевого множества (всего элементов i, хороших k, потому собственно и получаем, прим. пер.). Вероятность того что будет произведена перезапись конкретного элемента j из целевого множества R . Для того чтобы доказать что после окончания алгоритма каждый элемент S имел возможность попасть в целевое множество воспользуемся индукцией. После итерации i-1 вероятность того, что будет выбран элемент для целевого множества. Так как вероятность того что данный элемент будет перезаписан на следующей итерации , вероятность того что он не будет перезаписан на следующей итерации равна.Таким образом, вероятность того что любой элемент из множества S будет присутствовать в целевом множестве после итерации i определяется как произведение двух событий: элемент будет присутствовать в целевом множестве после предыдущей итерации, и не будет перезаписан (будет сохранён) на итерации i. Имеем . Значит результат справедлив для i, и следовательно справедлив по индукции.
...
Рейтинг: 0 / 0
11.08.2015, 06:41
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39027032
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Вообще-то для большого, но известного n, выборка k значений (где k<<n) делается гораздо проще, без сортировки и за k итераций.
...
Рейтинг: 0 / 0
11.08.2015, 14:03
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39027101
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dimitry SibiryakovВообще-то для большого, но известного n, выборка k значений (где k<<n) делается гораздо проще, без сортировки и за k итераций.

Это совсем другая задача
...
Рейтинг: 0 / 0
11.08.2015, 15:16
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39027117
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryDima T2. Заполняешь, сортируешь, в один проход проверяешь на повторы, заменяя повторы на новые случайные, затем снова сортируешь, проверяешь и т.д. пока проверка не покажет что повторов нет. Лишнего места не займет, но будут затраты на сортировку.

Кстати, обладает ли такой алгоритм свойством конечность? Особенно при достаточно больших n и k ? Как долго он может выполняться ?
Теорию вероятностей помню смутно, поэтому формулами не буду умничать, но при k значительно меньше n вероятность выпадения повтора небольшая, т.е. повторные проходы если и будут, то 1-3, не больше.
Самая тяжелая сортировка - первая, т.к. последующие (если будут) сортируют почти отсортированный массив.
...
Рейтинг: 0 / 0
11.08.2015, 15:26
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39027125
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryСудя по всему я нашёл решение данной задачи. Например алгоритм R
Можно поправить алгоритм и будет работать с интервалом 1...n.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
/*
  S has items to sample, R will contain the result
*/
ReservoirSample(n, R[1..k])
  // fill the reservoir array
  for i = 1 to k 
      R[i] := i

  // replace elements with gradually decreasing probability
  for i = k+1 to n 
    j := random(1, i)   //  important: inclusive range
    if j <= k
        R[j] := i


Только при k значительно меньше n мой велосипед может оказаться быстрее :)
...
Рейтинг: 0 / 0
11.08.2015, 15:33
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39027534
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TSashaMercuryпропущено...


Кстати, обладает ли такой алгоритм свойством конечность? Особенно при достаточно больших n и k ? Как долго он может выполняться ?
Теорию вероятностей помню смутно, поэтому формулами не буду умничать, но при k значительно меньше n вероятность выпадения повтора небольшая, т.е. повторные проходы если и будут, то 1-3, не больше.
Самая тяжелая сортировка - первая, т.к. последующие (если будут) сортируют почти отсортированный массив.

Допустим у нас 10 чисел, нам нужно выбрать три. Как долго мы будем случайно выбирать числа прежде чем у нас будет три уникальных ? А если числе 10^12 а уникальных нужно 10^12 - 1. Можем ли мы утверждать что если мы просто будем пропускать повторы мы за обозримый период времени получим множество уникальных чисел ?
...
Рейтинг: 0 / 0
12.08.2015, 06:20
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39027547
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercury Допустим у нас 10 чисел, нам нужно выбрать три. Как долго мы будем случайно выбирать числа прежде чем у нас будет три уникальных ?
Исходим из того что ГСЧ выдает числа с равной вероятностью.
Как с помощью теории вероятности посчитать не знаю, делаем проще. Тест
Код: plaintext
1.
 for(int i = 0; i < 30; i++) printf("%d,", rand()%10 + 1);


Результат5,10,1,1,9,6,6,7,6,9,7,4,3,5,7,5,5,10,2,8,9,9,1,5,10,7,8,4,4,5
в худшем случае 3 прохода для последовательности 5,7,5,5,10

SashaMercuryА если числе 10^12 а уникальных нужно 10^12 - 1. Можем ли мы утверждать что если мы просто будем пропускать повторы мы за обозримый период времени получим множество уникальных чисел ?
При 2k > n быстрее решать обратную задачу: выбрать лишние.
Это решается в один проход: выбираем одно лишнее, оставшиеся 10^12 - 1 требуемый результат :)
...
Рейтинг: 0 / 0
12.08.2015, 07:57
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39027555
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TSashaMercury Допустим у нас 10 чисел, нам нужно выбрать три. Как долго мы будем случайно выбирать числа прежде чем у нас будет три уникальных ?
Исходим из того что ГСЧ выдает числа с равной вероятностью.
Как с помощью теории вероятности посчитать не знаю, делаем проще. Тест
Код: plaintext
1.
 for(int i = 0; i < 30; i++) printf("%d,", rand()%10 + 1);


Результат5,10,1,1,9,6,6,7,6,9,7,4,3,5,7,5,5,10,2,8,9,9,1,5,10,7,8,4,4,5
в худшем случае 3 прохода для последовательности 5,7,5,5,10



где гарантия того что в следующий раз не потребуется 10 проходов ?
...
Рейтинг: 0 / 0
12.08.2015, 08:14
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39027557
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryгде гарантия того что в следующий раз не потребуется 10 проходов ?
Нужны гарантии: берешь и гоняешь алгоритм в цикле, собирая статистику.
...
Рейтинг: 0 / 0
12.08.2015, 08:20
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39027590
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TSashaMercuryгде гарантия того что в следующий раз не потребуется 10 проходов ?
Нужны гарантии: берешь и гоняешь алгоритм в цикле, собирая статистику.

Тогда мы говорим о статистике. Ни о чём более.
...
Рейтинг: 0 / 0
12.08.2015, 10:07
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39028258
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
SS
Судя по всему я нашёл решение данной задачи. Например алгоритм R

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
/*
  S has items to sample, R will contain the result
*/
ReservoirSample(S[1..n], R[1..k])
  // fill the reservoir array
  for i = 1 to k 
      R[i] := S[i] 

  // replace elements with gradually decreasing probability
  for i = k+1 to n 
    j := random(1, i)   //  important: inclusive range
    if j <= k
        R[j] := S[i]



Добавлю свой перевод обоснования из w.
Согласно алгоритму первоначально необходимо заполнить целевой массив R мощностью k первыми k элементами множества S. Следом необходимо перебрать оставшиеся в S элементы, до тех пор пока они не закончатся. На каждой итерации последнего перебора для каждого элемента s[i] алгоритм генерирует случайное число j из диапазона [1,i]. Если j<=k, то происходит присваивание r[j]<-s[i]. В действительности, на каждой итерации вероятность того, что будет выбран элемент для целевого множества (всего элементов i, хороших k, потому собственно и получаем, прим. пер.). Вероятность того что будет произведена перезапись конкретного элемента j из целевого множества R . Для того чтобы доказать что после окончания алгоритма каждый элемент S имел возможность попасть в целевое множество воспользуемся индукцией. После итерации i-1 вероятность того, что будет выбран элемент для целевого множества. Так как вероятность того что данный элемент будет перезаписан на следующей итерации , вероятность того что он не будет перезаписан на следующей итерации равна.Таким образом, вероятность того что любой элемент из множества S будет присутствовать в целевом множестве после итерации i определяется как произведение двух событий: элемент будет присутствовать в целевом множестве после предыдущей итерации, и не будет перезаписан (будет сохранён) на итерации i. Имеем . Значит результат справедлив для i, и следовательно справедлив по индукции.

Сразу не стал писать, но вот что меня смутило. В доказательстве чётко выделены события которые приведут к тому, что после i итерации элемент будет в целевом массив. Однако к таким событиям почему-то не отнесли вероятность того что конкретный элемент появится в целевом массиве именно на i итерации. Непонятно почему это не оговаривается.
...
Рейтинг: 0 / 0
13.08.2015, 04:58
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39088595
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Здравствуйте.
Решал на днях несколько задач. По трём из них у меня возникли некоторые вопросы. Возможно у кого-то будут соображения.

Перевод.
Первая задача не требует перевода, добавлю перевод 2 и 3:
4 -29
Некий Мистер Дал утверждает что разработал новую структуру данных типа очередь с приоритетом. Данная структура поддерживает операции Insert, Maximum, Extract Maximum, каждая из этих операций имеет асимптотику О(1). Докажите что он ошибается. (Подсказка: .... используйте тот факт что время исполнения сортировки

4 -30
БД содержит 10^4 записей в отсортированном порядке. 60% записей используются часто, остальные 40% редко. Предлагается два варианта организации БД:
1. Использовать одномерный массив и бинарный поиск
2. Создать два массива, в первом будет 60% записей(к ним обращение будет чаще всего), во втором остальные 40. Сначала ищем в первом, если не нашли, идём во второй. Бинарный поиск в каждом из массивов.

Какой подход лучше? Какой подход лучше если в обоих случаях использовать неотсортированный массив и линейный поиск ?


Мои соображения.
По задаче 3-28 вопросов практически нет, её можно решить следующим образом:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
//ниже псевдокод, я не тестировал его, основная идея всем понятна. Асимптотика О(n)
x[n];
before[n+1];
after[n+1];
m[n];
//ALGORITHM
//auxilary data
before[i=0..n]=1;
for(int i=0;i<n;++i){
   before[i+1]=before[i]*x[i];
}
after[i=0..n]=1;
for(int i=n-1;i<=0;--i){
   after[i]=after[i+1]*x[i];
}
//main array
for(int i=0;i<n;++i){
   x[i]=before[i]*after[i];
}



Q1) Может быть есть опечатки, но тут всё понятно. Вопрос такой: можно ли решить данную задачу иначе за линейное время(без использования деления) ?

Q2) Со второй задачей сложнее. Очевидным был бы следующий ответ: Так как Extract Maximum выполняется за O(1) то в таком случае сортировка возможна за O(n). Но 1. Зачем остальные части условия ? 2. Разве существует доказательство того что сортировка не может быть реализована за O(n) ?
Следовательно рассуждаю я скорее всего неверно(при решении данной задачи). Есть ли у вас какие-то идеи ?

Q3) Решение третьей задачи кажется совсем простым. В первом случае нужно задать такой вопрос, что лучше, log(n) или 2log(n) ? Конечно лучше хранить всё в одномерном упорядоченном массиве и использовать двоичный поиск.
Теперь пусть массивы будут неупорядоченны, и поиск будет линейный. В таком случае лучше разделить массив на два массива, и сначала осуществить поиск в первом массиве, а затем во втором. Но дело в том, что все рассуждения выше, как вы понимаете, относятся только к операции Search. Как провести комплексное рассуждение и сравнение я не знаю. Подскажите пожалуйста
...
Рейтинг: 0 / 0
28.10.2015, 07:58
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39089199
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
SashaMercuryМои соображения.
По задаче 3-28 вопросов практически нет, её можно решить следующим образом:Да, мне с ходу тот-же самый алгоритм придумался.

SashaMercuryQ1) Может быть есть опечатки, но тут всё понятно. Вопрос такой: можно ли решить данную задачу иначе за линейное время(без использования деления) ?А это ограничение я не понял. Какое такое деление автор задачи ожидает?
...
Рейтинг: 0 / 0
28.10.2015, 18:15
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39089200
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
SashaMercuryQ2) Со второй задачей сложнее. Очевидным был бы следующий ответ: Так как Extract Maximum выполняется за O(1) то в таком случае сортировка возможна за O(n). Но 1. Зачем остальные части условия ? 2. Разве существует доказательство того что сортировка не может быть реализована за O(n) ?
Следовательно рассуждаю я скорее всего неверно(при решении данной задачи). Есть ли у вас какие-то идеи ?Тоже не понял, к чему там подсказка. Я рассуждаю так:
а) Если в структуре данных хранится несколько элементов, то эта структура может рассматриваться как массив. В дальнейшем буду использовать это слово и сопутствующую терминологию.
б) Чтобы операция Maximum выполнялась за O(1), надо чтобы в данном массиве данных максимальный элемент был всегда четко указан. Это можно сделать двумя способами, либо хранить дополнительно индекс максимального элемента, либо держать в массив в сортированном состоянии.
в) Если массив изначально не сортирован, но мы имеем индекс на его максимальный элемент то чтобы выполнялась операция ExtractMaximum выполнялась за O(1) надо чтобы мы могли за O(1) найти новый максимальный элемент после экстракта предыдущего максимума. Значит нам нужно где-то хранить индекс предыдущего во величине элемента. Это проще всего сделать если хранить индекс предыдущего элемента вместе с самим элементами... Вывод - в случае хранения данных не в сортированном виде мы должны хранить его в связном списке.
г) Но в случае связанного списка для вставки элемента в правильное место (что бы сохранить сортированность списка), нам понадобится это место найти, а это уже обязательно O(n).
д) Если данные хранятся в виде сортированного индексированного массива, то для нахождения максимума достаточно взять его последний элемент, а для нахождения предыдущего максимально - предпоследний. Все просто и легко, Maximum и ExtractMaximum выполняются за O(1).
е) А если у нас сортированный индексированный массив, то операция вставки потребует найти те два элемента между которыми надо вставлять новый, а это как минимум O(log n). А потом еще двигать хвост массива чтобы освободить место под новый элемент, а это еще O(n).
Таким образом у нас и получается что структура данных у которой все три завяленные операции выполняются за O(1) не получается...
...
Рейтинг: 0 / 0
28.10.2015, 18:16
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39089215
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
SashaMercury 4 -30
БД содержит 10^4 записей в отсортированном порядке. 60% записей используются часто, остальные 40% редко.Не совсем. Там имеется 40% людей которые делают 60% запросов.
Это значит что результат поиска "своей" записи надо умножить на частоту обращений.

SashaMercuryQ3) Решение третьей задачи кажется совсем простым. В первом случае нужно задать такой вопрос, что лучше, log(n) или 2log(n) ? Конечно лучше хранить всё в одномерном упорядоченном массиве и использовать двоичный поиск.
Не совсем... К тому же у нас заранее известен n.
В случае одного общего массива мы имеем: 10000*log(10000)=132877.1238.
А в случае двух массивов мы имеем: 6000*log(4000) + 4000*log(6000)=71794.7057 + 50202.9871 = 121997.6928
Итого, два массива при бинарном поиске получаются чуть-чуть получше, примерно на 8%.

Аналогично для линейного:
Общий массив: 10К * 10К = 100М
Два массива: 6К*4К+4К*6К= 24К+24К = 48К
Выигрыш получается еще больше.
...
Рейтинг: 0 / 0
28.10.2015, 18:37
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39089226
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
White OwlSashaMercuryQ1) Может быть есть опечатки, но тут всё понятно. Вопрос такой: можно ли решить данную задачу иначе за линейное время(без использования деления) ?А это ограничение я не понял. Какое такое деление автор задачи ожидает?
Самый простой и эффективный алгоритм: все перемножить, затем делить на каждый элемент.
...
Рейтинг: 0 / 0
28.10.2015, 18:52
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39089234
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
White OwlSashaMercury 4 -30
БД содержит 10^4 записей в отсортированном порядке. 60% записей используются часто, остальные 40% редко.Не совсем. Там имеется 40% людей которые делают 60% запросов.
Неверный вывод. Сказано "часто", без конкретики, я так понимаю это точно не 60:40, может 100:1 или 1000:1
...
Рейтинг: 0 / 0
28.10.2015, 19:00
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39089235
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercuryНекий Мистер Дал утверждает что разработал новую структуру данных типа очередь с приоритетом. Данная структура поддерживает операции Insert, Maximum, Extract Maximum, каждая из этих операций имеет асимптотику О(1). Докажите что он ошибается. (Подсказка: .... используйте тот факт что время исполнения сортировки

Да. Мистер Дал имеет возможность создать такую структуру. Это может быть автомат (конечный?) который имеет
входы INSERT, EXTRACT_MAXIMUM... и бесконечное число состояний которое моделирует различные варианты входов.
Правда мистер Дал забыл сказать что ему возможно понадобится бесконечно большая память.
...
Рейтинг: 0 / 0
28.10.2015, 19:01
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39089269
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
Dima TWhite Owlпропущено...
А это ограничение я не понял. Какое такое деление автор задачи ожидает?
Самый простой и эффективный алгоритм: все перемножить, затем делить на каждый элемент.А ну да. Самый простой. Однако не самый эффективный :) Все-таки O(n) против O(n^2)
...
Рейтинг: 0 / 0
28.10.2015, 20:02
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39089273
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
Dima TWhite Owlпропущено...
Не совсем. Там имеется 40% людей которые делают 60% запросов.
Неверный вывод. Сказано "часто", без конкретики, я так понимаю это точно не 60:40, может 100:1 или 1000:1
Чего это вдруг неверный? "40% of whom known as good customers and who together account for 60% access to the database". Откуда ты взял вариативность?
...
Рейтинг: 0 / 0
28.10.2015, 20:05
| Ответить | Цитировать | Написать  
SSS. Некоторые задачи
    #39089292
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
White OwlDima Tпропущено...

Самый простой и эффективный алгоритм: все перемножить, затем делить на каждый элемент.А ну да. Самый простой. Однако не самый эффективный :) Все-таки O(n) против O(n^2)
с чего вдруг O(n^2)? Два прохода: первый перемножить, второй получить результат. Два цикла против трех и никакого лишнего расхода памяти.
White OwlDima Tпропущено...

Неверный вывод. Сказано "часто", без конкретики, я так понимаю это точно не 60:40, может 100:1 или 1000:1
Чего это вдруг неверный? "40% of whom known as good customers and who together account for 60% access to the database". Откуда ты взял вариативность?
Не буду спорить, оригинал не понимаю. Не силен в английском. Пользовался Сашиним переводом:
SashaMercuryБД содержит 10^4 записей в отсортированном порядке. 60% записей используются часто, остальные 40% редко.
...
Рейтинг: 0 / 0
28.10.2015, 20:30
| Ответить | Цитировать | Написать  
25 сообщений из 69, страница 2 из 3
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / SSS. Некоторые задачи
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39089226&tid=1340824]:
 0ms
get settings:
 6ms
get forum list:
 11ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 33ms
get topic data:
 6ms
get forum data:
 1ms
get page messages:
 39ms
get tp. blocked users:
 1ms
others: 208ms
total:  309ms
созд. / загр.: 309ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]