#11255: Сложно — но можно?

В институте был предмет с названием «Структуры и алгоритмы обработки данных». Нас учили реализовывать простые и двусвязные списки, деревья, графы и так далее. Заодно осваивали основы ООП — все эти структуры писали в виде классов. В методичке приводилась реализация всех структур и основных методов — самая базовая функциональность, а в качестве задания студентам предлагалось реализовать ещё какой-нибудь метод. Студенты отжигали не по-детски.

Написать функцию size() для списка? Нормальные люди для этого заводят переменную, обнуляют при создании массива, инкрементируют при вставке элемента и декрементируют при удалении. Но это не по фэн-шую: мы просто пересчитаем все элементы.

Надо вычислить сумму элементов списка, но писать итератор лень. Да и зачем, если в методичке есть замечательная функция seek(i), возвращая i-й элемент? Но в списке, в отличие от массива, невозможен прямой доступ к элементу, нужно просматривать все с начала списка, поэтому сложность будет квадратичной. А можно ещё написать цикл так: for(int i = 0; i < size(); i++) S += seek[i]. Это вообще замечательно: на каждую итерацию сначала выполним size(), которая просматривает весь список, а потом ещё просмотрим с помощью seek только i первых элементов.

Но один студент переплюнул всех. У него было задание написать функцию, сравнивающую два списка как множества: истина возвращалась, если элементы в списках одинаковые, независимо от порядка следования. Он сделал цикл от 0 до size() одного списка, а туда воткнул такой же цикл для второго. Сложность алгоритма получилась О(N^4)!

Комментарий:

Ещё интересное на этом сайте:

Анекдоты и картинки #8704865
#11252: Карманный мейнфрейм
Эпическое обращение к правообладателям
Огромная коллекция всех летних фэйлов 2013
Джаред Хасселхофф из "Bloodhound Gang" подтерся российским флагом (3 видео)
Криминальное прошлое участников «Дом-2» (22 фото)
Прикольные картинки (139 фото)
День ВДВ в Питере (8 фото)
Несуществующий флаг на здании ФСКН (1 фото)
Джаред Хасселхофф из "Bloodhound Gang" подтерся российским флагом (3 видео)
Положение руки расскажет все о мужчинах (1 картинка)
Прикольные картинки (144 фото)
Классные гифки (25 гифок)
Идеальный день ВДВ (5 фото)
Смешные комиксы (30 картинок)
Как Россия отмечала День Десантника (51 фото + видео)
Креативный гаджет для транспортировки кота (3 фото)
ТОП-10 историй о пропавших без вести людях (12 фото)
Как коммунальщики ремонтируют дороги (8 фото)
Ляпы в мировом кино (30 фото)

« все анекдоты и картинки