20 / 20 / 10
Регистрация: 19.05.2015
Сообщений: 704
|
||||||
1 | ||||||
Оптимизировать код10.11.2016, 19:47. Показов 929. Ответов 21
Метки нет (Все метки)
Первое число входного потока - количество чисел
Дальше идут те самые числа Надо найти кол-во пар чисел, для которых выполняется nums[i] <= nums[j] && nums[i] >= 0.9*nums[j] и наоборот Код готов, работает, но не хватает времени на выполнение задачи с большими объемами входа (до 1 000 000 000) Помогите оптимизировать
0
|
10.11.2016, 19:47 | |
Ответы с готовыми решениями:
21
Оптимизировать код Нужно оптимизировать код Нужно оптимизировать код Исправить и оптимизировать код |
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
|
10.11.2016, 20:02 | 2 |
Предварительно отсортировать входной массив, заменить nums[i] <= nums[j] на i<j.
0
|
20 / 20 / 10
Регистрация: 19.05.2015
Сообщений: 704
|
|
10.11.2016, 20:26 [ТС] | 3 |
Как это можно реализовать с минимальным количеством действий в циклах?
Точнее, будет ли оптимальный такой вариант: найти в массиве место, куда вставить, до него не трогать, после него все сдвинуть через переменную?
0
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
|
10.11.2016, 22:21 | 4 |
std::sort(nums,nums+count). Или вдумчиво читать то же "Искусство Программирования" Дональда Кнута, где разбираются в том числе и методы сортировки.
1
|
20 / 20 / 10
Регистрация: 19.05.2015
Сообщений: 704
|
|
10.11.2016, 22:31 [ТС] | 5 |
Прикол в том, что сортировать готовый массив - значит выходить сразу из всех циклов, потом еще сортировка время, а потом новые циклы, то есть логичнее делать это более динамически, сразу вставляя элемент куда надо
Но попробую, может сработает
0
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
|
10.11.2016, 22:39 | 6 |
Прикол в том, что прежде чем рассуждать о логике, надо сесть и прикинуть на пальцах вычислительную сложность. Вставка элемента в середину массива - линейное время (потому что все что после вставки надо сдвинуть). Число вставок у вас растет опять-же линейно. Итого, время сожранное вашей "логичной" сортировкой растет по квадрату. Тогда как у нормальных людей оно N*log(N). Если же вдумчиво читать Кнута и (очень) щедро жертвовать память Богу-Машине, можно и линейное время попробовать выжать.
0
|
What a waste!
1610 / 1302 / 180
Регистрация: 21.04.2012
Сообщений: 2,733
|
|
10.11.2016, 22:40 | 7 |
У предложенного варианта с сортировкой асимптотическая сложность меньше, чем в оригинале, так что...
0
|
20 / 20 / 10
Регистрация: 19.05.2015
Сообщений: 704
|
|
10.11.2016, 22:40 [ТС] | 8 |
0
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
|
10.11.2016, 22:44 | 9 |
Какая разница сколько там единиц? Если массив отсортирован, элемент с меньшим индексом по определению не может быть больше элемента с большим индексом. И выражение nums[i] <= nums[j] эквивалентно выражению i<j. Дальше вас должно осенить что коли так, то for (int j = 0; можно заменить на for (int j = i+1;, а сравнение i<j вообще выкинуть.
0
|
20 / 20 / 10
Регистрация: 19.05.2015
Сообщений: 704
|
||||||
10.11.2016, 22:52 [ТС] | 10 | |||||
С учетом всего сказанного вышел такой код
0
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
|
10.11.2016, 22:54 | 11 |
Ох...
0
|
1 / 1 / 0
Регистрация: 10.11.2016
Сообщений: 12
|
|
10.11.2016, 22:58 | 12 |
Дан массив А(20). Найти максимальный элемент среди положительных элементов массива А и сформировать массив Р(20), у которого вначале расположены элементы массива А с нечетными индексами, затем с четными.
Как сделать на с++? голова не варит уже(((
0
|
20 / 20 / 10
Регистрация: 19.05.2015
Сообщений: 704
|
|
10.11.2016, 23:06 [ТС] | 13 |
Ничего не изменилось....
Вопросик по-ходу: по быстродействию вложенные ифы дольше логического и?
0
|
What a waste!
1610 / 1302 / 180
Регистрация: 21.04.2012
Сообщений: 2,733
|
|
10.11.2016, 23:08 | 14 |
Игорь2001, можно так же заметить, что если nums[i] >= 0.9*nums[j], то и nums[i + 1] >= 0.9*nums[j]
0
|
20 / 20 / 10
Регистрация: 19.05.2015
Сообщений: 704
|
|
10.11.2016, 23:13 [ТС] | 15 |
Чуть подробнее, я не вижу, откуда это вытекает
То есть внешний цикл можно не i++, а i +=2 ?
0
|
What a waste!
1610 / 1302 / 180
Регистрация: 21.04.2012
Сообщений: 2,733
|
|
10.11.2016, 23:25 | 16 |
Игорь2001, nums[i] <= nums[i + 1] && nums[i] >= 0.9*nums[j] => nums[i + 1] >= 0.9*nums[j].
Добавлено через 6 минут Нет, можно j начинать не с i+1, а с предыдущего j.
0
|
20 / 20 / 10
Регистрация: 19.05.2015
Сообщений: 704
|
|
10.11.2016, 23:26 [ТС] | 17 |
0
|
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
|
||||||
10.11.2016, 23:30 | 18 | |||||
Ну, тады попробуйте:
0
|
What a waste!
1610 / 1302 / 180
Регистрация: 21.04.2012
Сообщений: 2,733
|
||||||
10.11.2016, 23:33 | 19 | |||||
Игорь2001, примерно так
1
|
20 / 20 / 10
Регистрация: 19.05.2015
Сообщений: 704
|
|
10.11.2016, 23:46 [ТС] | 20 |
Уже лучше, с большими числами успевает, сейчас еще с типами данных поработаю, вроде не влазит иногда...
А можете чуть-чуть логику объяснить, пожалуйста Добавлено через 3 минуты Да, для ответа надо было лонг Добавлено через 3 минуты Можете, пожалуйста примерно объяснить работу этого кода
0
|
10.11.2016, 23:46 | |
10.11.2016, 23:46 | |
Помогаю со студенческими работами здесь
20
Оптимизировать и минимализировать код Помогите оптимизировать код Как оптимизировать код? Помогите оптимизировать код Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |