Этот вопрос требует некоторой подготовки.
http://igoro.com/archive/big-oh-in-the-parallel-world/
«Метод 1» в этой ссылке подробно описывает нотацию для описания влияния параллелизма на алгоритмическую временную сложность. Мне очень нравится этот метод описания, но это единственное место, где я его нашел.
Мой вопрос заключается в следующем: почему это обозначение не используется чаще?
В самом описании метода есть одно объяснение: «Чтобы перемножить две матрицы 100×100, нам понадобится машина с 10 000 процессорами». Эта цитата, кажется, предполагает, что 10 000 процессоров совершенно неразумно ожидать.
Мой опровержение:
https://en.wikipedia.org/wiki/Manycore_processor
Самый большой суперкомпьютер в мире на данный момент, Taihu Light, содержит в общей сложности 40960*256 = 10485760 ядер. Не у всех есть доступ к суперкомпьютеру, такому как Taihu Light, но с постоянно набирающей популярность облачной обработкой я не вижу причин, по которым процессоры с 10 000 ядер и выше не будут широко доступны для использования в ближайшем будущем. Кроме того, средний графический процессор уже имеет 1000 ядер. Они более специализированы, чем ядра ЦП, но это не главное.
Так как примеров этой нотации очень мало, я также приведу свой собственный пример, используя эквивалентное описание, которое я называю нотацией больших денег.
Скажем, у нас есть идеально сбалансированное дерево с коэффициентом ветвления b. Все узлы, кроме одного, содержат логическое значение false, а последний содержит логическое значение true. Мы хотим найти и вернуть этот истинный узел.
Используя поиск в ширину, время выполнения Big-O для нахождения истинного узла будет равно O(|V|+|E|) == O(b^d), где b — коэффициент ветвления, а d — глубина дерево.
Однако, если мы предположим, что у нас есть бесконечное количество процессоров, каждый с конечными вычислительными возможностями, то обозначение больших денег будет следующим: $O(b^d -> d). Это говорит о том, что на 1 процессоре алгоритм занял бы время O(b^d), но по мере увеличения количества процессоров временная сложность приближается к d, глубине дерева. Это связано с тем, что в каждом ложном узле мы можем создать еще b процессов для поиска каждого из этих узлов b дочерних элементов. Поскольку у нас бесконечные ядра, все эти процессы могут работать параллельно. Вот почему я называю это обозначением больших денег. Сложность времени уменьшается с увеличением вычислительной мощности, вычислительная мощность увеличивается по мере того, как вы вкладываете больше денег в Amazon/Microsoft/Google/YourFavoriteCloudProvider.
Повторю еще раз свой вопрос. Почему нотация, подобная этой, не находит более широкого применения? Спасибо!
