Блог пользователя Rap_Promoter

Как петросяны готовятся к олимпиадам
Автор Rap_Promoter, 12 лет назад, По-русски

Вот такой вот продукт отечественного юморка получился в результате подготовки вместе с GShark и zakharvoit к открытой московской олимпиаде.

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Я просто напишу, что Прима можно несложно написать за M+NlogN и совсем легко(особенно на С++) за MlogN.
И да, кстати, в Краскале сортировка за MlogM.
Короче, я всегда считал, что это довольно схожие алгоритмы и выбор между ними — вопрос вкуса.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

    А я их вообще не различаю:(

    Пишу что-то, оно каркас находит — и ладно.

    Когда-то запутался в этом — прочел об алгоритме Прима, алгоритме Крускала, алгоритме Прима-Крускала... Некоторые авторы еще что-то оригинальное придумывают и называют одно и то же разными именами...

    И я решил не забивать себе мозг:)

    → Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    О(m * log(m)) и O(m * log(n)) здесь одно и то же т.к. m < n^2

    → Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +66 Проголосовать: не нравится

Если число рёбер близко к N^2, то алгоритм Прима будет асимптотически быстрее ;)

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Петросян, ты готов к олимпиаде.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +63 Проголосовать: не нравится

    Спасибо, тренер. А вообще — враки, мы так не готовимся.

    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Ну насчет бро — не бро не знаю... Может я криворукий, но Крускала здесь запихнуть не смог. Спас меня только Прим.

→ Ответить