ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / возможно ли отсортировать элементы в массиве за о(n)?
25 сообщений из 51, страница 2 из 3
  2  все
возможно ли отсортировать элементы в массиве за о(n)?
    #38887965
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Anatoly MoskovskymaytonУникальные целые в один проход. Биткартой.
А где тут O(n)?
Лучше спроси где тут сортировка. Ее нет. Но - с точки зрения пользователя данные
отсортированы.
...
Рейтинг: 0 / 0
25.02.2015, 08:48
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38887981
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
mr_virtusпривет.

попался вопрос - в сабже.

ответ - возможно для массивов некоторых типов.

Подскажите, пожалуйста, как это?

как писали выше, действительно существуют частные случаи на практике, когда такое возможно.

Теоретически, имея неограниченный объём памяти, и изменив смысл слова "сортировка", возможно за один проход получить набор данных, чтение которых(определённым образом) даст нам упорядоченный набор. Существующие ограничения по данному вопросу накладываются как ни странно не математикой, а устройством ВМ.
...
Рейтинг: 0 / 0
25.02.2015, 09:16
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38887984
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Мне часто говорят в Сообществе (нашем) о том, что математика и программирование разные вещи. Так почему до сих пор основные алгоритмы (такие как сортировка например) основаны на математике и упираются в nlogn , а так называемые сортировки распределениями хилая тень того, что могло, и что должно быть
...
Рейтинг: 0 / 0
25.02.2015, 09:27
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38887988
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
SSМне часто говорят в Сообществе (нашем) о том, что математика и программирование разные вещи. Так почему до сих пор основные алгоритмы (такие как сортировка например) основаны на математике и упираются в nlogn , а так называемые сортировки распределениями хилая тень того, что могло, и что должно быть

а почему понятно. Потому что мы ограничены устройством современной ВМ.
...
Рейтинг: 0 / 0
25.02.2015, 09:29
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38888075
mr_virtus
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mr_virtus
Участник
Всем спасибо.
...
Рейтинг: 0 / 0
25.02.2015, 10:49
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38888137
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
mr_virtus,
Можно за 8*O(n)
...
Рейтинг: 0 / 0
25.02.2015, 11:22
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38888416
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
SashaMercury...Теоретически...и изменив смысл слова "сортировка"...
Изменив смысл слова, можно скорость сделать O( 0 ).

В linux такое чудо-устройство есть, /dev/null называется.

IMHO & AFAIK
...
Рейтинг: 0 / 0
25.02.2015, 13:48
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38889600
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
maytonЛучше спроси где тут сортировка. Ее нет. Но - с точки зрения пользователя данные
отсортированы.
Ну вот тестовый массив из 2х элементов.
Код: plaintext
[1, 9999999999999]

Занесли его в битовую карту. И что видит пользователь?
А ничего он не видит. Кучу нулевых битиков и только местами единички, но их еще разглядеть надо.
А сканировать по битовой карте, это уже не O(n)
...
Рейтинг: 0 / 0
26.02.2015, 15:38
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38889610
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ты долго-долго искал наихудший случай.
...
Рейтинг: 0 / 0
26.02.2015, 15:40
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38889615
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
maytonТы долго-долго искал наихудший случай.
Нет, я просто забыл про этот топик ))
А искать там не надо - оно на поверхности.
...
Рейтинг: 0 / 0
26.02.2015, 15:41
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38889698
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну в конце-то концом мой месседж звучит по другому. Я ищу про-активное решение.
На несколько шагов вперёд. Мне говорят - надо отсортировать. Я говорю - не существует
такой постановки. Дайте шаг №2. Что потом будете делать? И я дам решение.

Сферическими сортировками в вакууме пускай занимется Кнут и Вирт с Хоаром.
А у нас - предметная область и аппаратное обеспечение. И требования бизнеса.
...
Рейтинг: 0 / 0
26.02.2015, 16:24
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38889721
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
maytonСферическими сортировками в вакууме пускай занимется Кнут и Вирт с Хоаром.
А у нас - предметная область и аппаратное обеспечение. И требования бизнеса.
Зря так про Вирта. Вирт как раз учитывал аппаратное обеспечение - потому и не котировал функциональщину.
...
Рейтинг: 0 / 0
26.02.2015, 16:35
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38890709
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Anatoly Moskovskyсканировать по битовой карте, это уже не O(n)
Разве? Поиск всех значений это именно O(n). Проверка одного значения это O(1).
...
Рейтинг: 0 / 0
27.02.2015, 14:59
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38890904
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Anatoly Moskovskyсканировать по битовой карте, это уже не O(n)
Dimitry SibiryakovРазве? Поиск всех значений это именно O(n). Проверка одного значения это O(1).
Как я понял, имелось в виду, что N - разное.

Если делаем массив для подсчета на 1 000 000 элементов и выполняем сортировку 2-х чисел:
[1, 999 999]
То потребуется 2 операций вставки и 1 000 000 операций просмотра для "истинной" сортировки 2 чисел с выдачей результата

Т.е. сложность сортировки получает O1( N ) + O2( 1 000 00 ). Оно конечно "линейно", но счастье сомнительное.
...
Рейтинг: 0 / 0
27.02.2015, 17:03
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38890938
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Бонжур мезами.

Представим себе фильтр Блума. С "нужными" параметрами. Макс число элементов e.t.c.
C "хорошими" (сцуко) параметрами.

Код: javascript
1.
bloom = new Bloom(massiv.length);


Добавим в него ваш массивчик.

Код: javascript
1.
2.
3.
4.
5.
6.
7.
mini = int.max;
maxi = int.min;
for(int i : massiv){
   bloom.add(massiv[i]);
   maxi=max(massiv[i]);
   mini=min(massiv[i]);
}



(Определим границы походу)

Выведем все элементы из диапазона.

Код: javascript
1.
2.
3.
for(int i : mini..maxi){
   if (bloom.has(i)) println i;
}



Силь ву пле! Они отсортированы! И найдите мне здесь оценку сортировки.

Жду.
...
Рейтинг: 0 / 0
27.02.2015, 17:34
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38890973
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
maytonСиль ву пле! Они отсортированы! И найдите мне здесь оценку сортировки.
O1(n) + O2(max-min).

Причем второе слагаемое настолько зависит от данных, что ваша сортировка может вообще не закончиться в обозримом будущем.
Пример с данными вмещающимися в long на большинстве современных платформ:
[1, 2^64-1]

Удачи в ожидании завершения вашего цикла ))
...
Рейтинг: 0 / 0
27.02.2015, 18:04
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38891020
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Спасибо Толик. Только проясни откуда ты взял O1(n) + O2(max-min) ?

И тебе удачи.
...
Рейтинг: 0 / 0
27.02.2015, 19:00
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38891045
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
mayton,

Отсюда:
for(int i : massiv)
for(int i : mini..maxi)
...
Рейтинг: 0 / 0
27.02.2015, 19:20
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38891190
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Это не сортировка бро. Это input/output. Альфа и омега любого алгоритма.
Без этих элементов вообще ничего не работает.

Но мой вопрос - философский. Вы оцениваете временную сложность
сортировки - я вам показал что ее просто нет. Как можно оценивать
то чего нет?
...
Рейтинг: 0 / 0
28.02.2015, 00:06
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38891224
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
mayton,

Нет сортировки - значит ОФФТОПИК
...
Рейтинг: 0 / 0
28.02.2015, 03:19
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38891258
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да но выхлоп программы - сортированный.

Как-же так? Сортировки нет но пользователь доволен.
...
Рейтинг: 0 / 0
28.02.2015, 09:48
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38891361
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
maytonно пользователь доволен.
А вот это уже фантазии.
Не может быть пользователь доволен если массив из двух элементов выводится (видите, уже не пишу сортируется) несколько миллиардов лет
...
Рейтинг: 0 / 0
28.02.2015, 16:18
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38891383
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Неа.
...
Рейтинг: 0 / 0
28.02.2015, 17:25
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38891431
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
maytonСортировки нетСортировка таки есть. Это сравнений чисел нет. Такие алгоритмы так и называются - сортировка без сравнений.
...
Рейтинг: 0 / 0
28.02.2015, 19:25
| Ответить | Цитировать | Написать  
возможно ли отсортировать элементы в массиве за о(n)?
    #38899151
Kaprizka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kaprizka
Участник
А функция bloom.has(i) что, быстрая?
...
Рейтинг: 0 / 0
09.03.2015, 20:59
| Ответить | Цитировать | Написать  
25 сообщений из 51, страница 2 из 3
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / возможно ли отсортировать элементы в массиве за о(n)?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=38889698&tid=1341071]:
 0ms
get settings:
 8ms
get forum list:
 13ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 179ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 70ms
get tp. blocked users:
 1ms
others: 240ms
total:  528ms
созд. / загр.: 528ms
x
x
Закрыть


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