Архив рубрики: Алгоритмы

Что скрывает O-нотация?

Для оценки времени работы алгоритмов принято использовать O-нотацию. Она задает верхнюю асимптотическую сложность алгоритма. То есть, она показывает как, при прочих равных, изменяется время работы алгоритма при изменении размера входных данных. Например, если некоторый алгоритм имеет сложность O(n*n), то при увеличении размера входных данных в 3 раза, время его работы увеличится примерно в 9 (3*3) раз.

Ее же используют для сравнения эффективности алгоритмов. Так, если первый алгоритм имеет сложность O(n*n), а второй — O(n), то последний значительно быстрее первого. При увеличении размера входных данных в 3 раза, время работы первого алгоритма увеличится примерно в 9 раз, а второго — в три раза. Почему примерно?

Читать полностью →

Получение списка доступных COM портов

При программировании COM портов полезно иметь возможность получать список доступных портов на компьютере. Эта задача встречается настолько часто, что я решил затронуть ее в своем блоге. Читать полностью →

Полемика о времени жизни объекта

В своей предыдущей статье я представил алгоритм использования функции PulseEvent в качестве спускового крючка. Такой подход предполагает, что исполнительный поток создается во время старта программы и уничтожается только тогда, когда основная программа завершает свою работу. С таким подходом могут не все согласиться. Читать полностью →

Функция PulseEvent в роли спускового крючка

Функция PulseEvent предназначена для кратковременного перевода объекта событие в свободное состояние с его последующим возвратом в занятое состояние. Обычно в литературе по Windows API ей уделяется мало внимания. Тем не менее, её можно использовать в качестве спускового крючка при управлении потоком. О том, как это сделать, я сегодня и расскажу. Читать полностью →

Алгоритм подсчета счастливых билетов

Задача вычисления количества счастливых билетов известна давно. Ее задавали практически любому школьнику, обучающемуся программированию. В интернете можно найти множество ее решений на разных языках программирования. Все эти варианты сводятся к перебору всех существующих билетов и проверке их на «счастливость». Получается миллион вариантов.

Но данную задачу можно решить и другим способом, перебрав всего тысячу вариантов.

Читать полностью →