Обсуждение:СНМ (списки с весовой эвристикой)

• "с помощью списка", почему список только один?
• слишком большие абзацы
• картинки слишком большие, надо поставить на страницу миниатюры со ссылками
• дефисы вместо тире, что не соответствует правилам оформления. Дальше читать не стал.

--Андрей Шулаев 23:31, 23 апреля 2012 (GST)

• Определение
  • Не стоит использовать блок "определение" в данном случае.
  • "улучшение наивной реализации СНМ" — какой?
  • Детали (например про то, что в для каждого списка хранится длина) в начале конспекта неуместны, надо просто описать идею эвристики.
  • Также в начале конспекта неплохо будет описать мотивацию для введения этой эвристики — улучшение времени работы с [math]O(n^2)[/math] до [math]O(n \log n)[/math].
• Проблема наивной реализации
  • Первое предложение криво написано, лучше разбить на два: сначала о том, что реализация — на списках, потом о том, что из себя представляет каждый список
  • Не стоит писать "мы можем объединить два списка за O(1)". Можно слить два списка без указателей на голову из каждого за O(1), если считать, что в каждом списке хранится указатель на последний элемент. Лучше просто написать что слияние таких списков занимает линейное время.
  • Выражения "n - 1" и подобные занести в тег tex
• Реализация с весовой эвристикой
  • Первое предложение слишком длинное и криво написано, переписать.
  • При написании конспектов не стоит использовать слово "давайте".
  • О том, как называется эта оптимизация, уже написано ранее.
  • О модификации используемых структур данных (хранение длины) нужно написать как раз в этом разделе
  • Также здесь нужно привести псевдокод процедуры слияния с использованием описанной эвристики.
• Доказательство
  • Формулировка утверждения всё ещё скопирована из Кормена.
  • Не надо два раза писать "Оценим количество", напишите как-нибудь по-другому.
  • Во втором абзаце пунктуационные ошибки, надо исправить.
  • Вместо "можно за O(1)" должна быть ссылка на псевдокод в предыдущей секции,
  • Начинать предложение с выражения "O(m)" нельзя, надо переписать.

--Андрей Шулаев 15:39, 25 апреля 2012 (GST)