Ekaterina Yaryshkina edited section_n_m_n_m__.tex  almost 8 years ago

Commit id: ebef48a3bd3fbca76d947ccc51c2c9b49fd295fb

deletions | additions      

       

Алгоритм вычисления ... соответствует математическому определению ошибки, данному выше. Сложность по времени (от n и m, где n и m - размеры списков на входе алгоритма) составляет ...  Сложность по требуемой памяти ... Вычисляются две разные вещи: (1) Err и (2) Uniq. Наверняка, существуют быстрые однопроходные алгоритмы для вычисления Uniq "количество уникальных объектов в каждом списке". Либо найти такие алгоритмы и оценку сложности в литературе, либо предложить алгоритм и свою оценку сложности. Думаю, сложность будет O(n) для вычисления Uniq...