История изменений

Не нужно строить суперлабу, чтобы измерить потребление памяти и cache misses на задаче «вход-выход». Достаточно time -v и perf.

Кроме того, там нужно было хранить дерево. А в дереве adjacency lists будет иметь известное число элементов 2*(|V|-1), т.е. большинство внутренних векторов будут очень короткими.

Если вы придрались к слову «максимально», то, как мне казалось очевидно, это гипербола (в литературном смысле). Кроме суперизученных задач вроде сортировок вообще мало где есть пруф нижней оценки сложности, и к практической архитектуре процессора вся эта теория слабо применима. Уверен, вы и сами ни разу «формально не пруфали индуктивные гипотезы «оптмизированного» кода». Для индустрии нормально просто сравнивать 2 кода А и Б железе X и Y, подсчитывая попугаи.

Не нужно строить суперлабу, чтобы измерить потребление памяти и cache misses на задаче «вход-выход». Достаточно time -v и perf.

Кроме того, там нужно было хранить дерево. А в дереве adjacency lists будет иметь известное число элементов 2*(|V|-1), т.е. большинство внутренних векторов будут очень короткими.

Если вы придрались к слову «максимально», то, как мне казалось очевидно, это гипербола (в литературном смысле). Кроме суперизученных задач вроде сортировок вообще мало где есть пруф нижней оценки сложности, и к практической архитектуре процессора вся эта теория слабо применима. Уверен, вы и сами ни разу формально не пруфали индуктивные гипотезы «оптмизированного» кода. Для индустрии нормально просто сравнивать 2 кода А и Б железе X и Y, подсчитывая попугаи.