Size: a a a

2020 August 26

V🇺

Vladislav 🇺🇸🚜🇷🇺... in pro.algorithms
Evgenii Zheltonozhskii🇮🇱
А кто может вкратце рассказать почему L notation is a thing
🤔 хороший вопрос
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺... in pro.algorithms
возможно потому что у нее есть удобные свойства?
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺... in pro.algorithms
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Vladislav 🇺🇸🚜🇷🇺
возможно потому что у нее есть удобные свойства?
Ну почему есть больше одного алгоритма чья сложность описывается такой штукой
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Или это единственное что пруфается?
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺... in pro.algorithms
Evgenii Zheltonozhskii🇮🇱
Или это единственное что пруфается?
предположу что так (или единственное что пруфается адекватно)
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Либо есть какая то emergent structure которая такое дает
источник

ПК

Паша Калугин... in pro.algorithms
Паша Калугин
У меня возникла следующая идея: запустить поиск в глубину, хранить путь от корня до нашей вершины. Если мы в какой-то момент пришли в вершину, в которой мы уже побывали, и при этом мы пришли не из неё, то мы нашли цикл, помечаем соотв. суффикс пути как цикл.
Ну вроде это работает
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺... in pro.algorithms
Evgenii Zheltonozhskii🇮🇱
Либо есть какая то emergent structure которая такое дает
скорее нет чем да
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Последнее прикольно кстати
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺... in pro.algorithms
Evgenii Zheltonozhskii🇮🇱
Последнее прикольно кстати
но кажется что тривиально?
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺... in pro.algorithms
это кстати скриншот из статьи Ленстры, которая примерно только из него и состоит: https://link.springer.com/referenceworkentry/10.1007%2F978-1-4419-5906-5_459
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Vladislav 🇺🇸🚜🇷🇺
но кажется что тривиально?
Почему
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺... in pro.algorithms
pi(x)<x
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Но L_x это не O(f) же
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Если я не тупанул конечно это скорее Teta
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺... in pro.algorithms
тут так определяют
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Vladislav 🇺🇸🚜🇷🇺
тут так определяют
Ну поправь если я ошибаюсь, но например f(x)=1 не будет L_x[1,1]
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺... in pro.algorithms
🤔 похоже, да
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺... in pro.algorithms
источник