От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.
Из предыдущей части можно сделать вывод, что если мы сможем отбросить все эти декоративные константы, то говорить об асимптотике функции подсчёта инструкций программы будет очень просто. Фактически, любая программа, не содержащая циклы, имеет f( n ) = 1, потому что в этом случае требуется константное число инструкций (конечно, при отсутствии рекурсии — см. далее). Одиночный цикл от 1 до n, даёт асимптотику f( n ) = n, поскольку до и после цикла выполняет неизменное число команд, а постоянное же количество инструкций внутри цикла выполняется n раз.
На хабре не очень много уроков по созданию игр, почему бы не поддержать отечественных девелоперов?
Представляю вам свои уроки, которые учат создавать игры на C++ с использованием SDL!
Что нужно знать
Хотя бы начальные знания C++ (использовать будем Visual Studio)
Терпение
О чем эта часть?
Мы создадим каркас для всех игр, в качестве отрисовщика будем использовать SDL. Это библиотека для графики.
В следующих постах будет больше экшена, это лишь подготовка :)
Часть 1: Введение. Часть 2: Многопоточность
Часть 3: Рендеринг (Прим. пер. — в процессе перевода)
Часть 4: Doom classic — интеграция (Прим. пер. — в процессе перевода)
26 ноября 2012 ID Software выпустила исходный код Doom 3 BFG edition (всего через месяц после появления игры на прилавках магазинов). Движок idTech4, которому уже почти 10 лет, был обновлен решениями, используемыми в idTech 5 (Rage — первая игра на этом движке), и с его исходным кодом ознакомиться было очень интересно.
Я бы назвал движок «idTech4 улучшенный», т.к. по сути это idTech4, но с использованием элементов idTech5:
Часть 1: Введение Часть 2: Многопоточность
Часть 3: Рендеринг (Прим. пер. — в процессе перевода)
Часть 4: Doom classic — интеграция (Прим. пер. — в процессе перевода)
Движок для Doom III был написан в период с 2000 по 2004 год, в то время, когда большинство ПК были однопроцессорными. Хотя архитектура движка idTech4 разрабатывалась с учетом поддержки SMP, это закончилось тем, что поддержка многопоточности делалась в последнюю минуту (см. интревью с Джоном Кармаком).
Преподаватель из Стэнфордского университета Кит Шварц (Keith Schwarz) уже несколько лет пополняет свой архив интересного кода — образцы самых лучших алгоритмов и структур данных, когда-либо изобретённых человечеством (Шварц весьма амбициозно оценивает свою коллекцию).
Примеры на сайте преимущественно закодированы в C++, поскольку STL предоставляет прекрасную базу для выражения алгоритмов, работающих с различными типами данных. Структуры данных реализованы на Java.
Кит Шварц дает разрешение использовать свой код всем желающим без всяких ограничений.
Часть 1: Введение. 