Bash.org.ru IT Happens Истории ## 11001 – 12000

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

12:45 05.08.2013, IT happens

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

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

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

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