Вообще, НАТ и ПАТ технологии, которые как правило решают немного разные задачи.
Если вопрос академический, то мешьше всего операций требуется при отсутсвии обоих этих технологий.
Далее следует статическая трансляция и т.д., а в хвосте плетется динамическая трансляция с оверлоадом портов.
ЗЫ В зависимости от модели маршрутизатора эти технологии могут осуществляться программно (Cisco ISR 8xx - 72xx, ASA, PIX, *nix, Windows) и аппаратно (тяжелые катки, 76xx, ASR?).
Другой вопрос, что нагрузка на ресурсы порой даже в программых решениях бывает настолько мала, что заметить ее не просто.
Всего хорошего