Обсуждение:СНМ (списки с весовой эвристикой) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «* "с помощью списка", почему список только один? * слишком большие абзацы * картинки слишко...»)
 
 
Строка 4: Строка 4:
 
* дефисы вместо тире, что не соответствует правилам оформления. Дальше читать не стал.
 
* дефисы вместо тире, что не соответствует правилам оформления. Дальше читать не стал.
 
--[[Участник:Андрей Шулаев|Андрей Шулаев]] 23:31, 23 апреля 2012 (GST)
 
--[[Участник:Андрей Шулаев|Андрей Шулаев]] 23:31, 23 апреля 2012 (GST)
 +
 +
* '''Определение'''
 +
** Не стоит использовать блок "определение" в данном случае.
 +
** "улучшение наивной реализации СНМ" — какой?
 +
** Детали (например про то, что в для каждого списка хранится длина) в начале конспекта неуместны, надо просто описать идею эвристики.
 +
** Также в начале конспекта неплохо будет описать мотивацию для введения этой эвристики — улучшение времени работы с <tex>O(n^2)</tex> до <tex>O(n \log n)</tex>.
 +
* '''Проблема наивной реализации'''
 +
** Первое предложение криво написано, лучше разбить на два: сначала о том, что реализация — на списках, потом о том, что из себя представляет каждый список
 +
** Не стоит писать "мы можем объединить два списка за O(1)". Можно слить два списка без указателей на голову из каждого за O(1), если считать, что в каждом списке хранится указатель на последний элемент. Лучше просто написать что слияние таких списков занимает линейное время.
 +
** Выражения "n - 1" и подобные занести в тег tex
 +
* '''Реализация с весовой эвристикой'''
 +
** Первое предложение слишком длинное и криво написано, переписать.
 +
** При написании конспектов не стоит использовать слово "давайте".
 +
** О том, как называется эта оптимизация, уже написано ранее.
 +
** О модификации используемых структур данных (хранение длины) нужно написать как раз в этом разделе
 +
** Также здесь нужно привести псевдокод процедуры слияния с использованием описанной эвристики.
 +
* Доказательство
 +
** Формулировка утверждения всё ещё скопирована из Кормена.
 +
** Не надо два раза писать "Оценим количество", напишите как-нибудь по-другому.
 +
** Во втором абзаце пунктуационные ошибки, надо исправить.
 +
** Вместо "можно за O(1)" должна быть ссылка на псевдокод в предыдущей секции,
 +
** Начинать предложение с выражения "O(m)" нельзя, надо переписать.
 +
--[[Участник:Андрей Шулаев|Андрей Шулаев]] 15:39, 25 апреля 2012 (GST)

Текущая версия на 14:39, 25 апреля 2012

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

--Андрей Шулаев 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)

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Обсуждение:СНМ_(списки_с_весовой_эвристикой)&oldid=21245»