Перевод Worst case space complexity

Question

[Дмитрий]

Делаю перевод статьи по алгоритмам сортировки. Хотел бы узнать как лучше будут смотреться на русском языке следующие термины:

Worst case performance: O(n2)
Best case performance: O(n)
Average case performance: O(n2)
Worst case space complexity: O(1) auxiliary

Answer 1

[Ocelot]

Worst case performance — вычислительная сложность в худшем случае (имеется в виду случай организации входных данных)
Best case performance — вычислительная сложность в лучшем случае
Average case performance — вычислительная сложность в среднем (?)
Worst case space complexity — пространственная сложность в худшем случае (характеризуется ростом требуемого объёма памяти при росте размерности задачи). Слово «auxiliary», кажется, вырвано из контекста.
И n2 — это, конечно, n² (n квадрат).

Comments

[Дмитрий]

n2 имеется в виду квадрат, а слово из контекста не вырвано
Мне кажется Worst case space complexity — это пространственная сложность алгоритма.

Answer 2

[Андрей]

Я бы предложил

Вычислительная сложность в худшем случае
Вычислительная сложность в лучшем случае
Средняя вычислительная сложность
Требования к памяти в худшем случае

Answer 3

[Андрей]

Ну вот мне как человеку, имеющему диплом переводчика, дословные кальки с языка оригинала всегда режут слух. Конечно, если термин именно в таком виде стал общеупотребительным в специальной литературе, то тут ничего не поделаешь. Но там где такой ситуации нет, мне кажется нужно использовать более доступный (близкий к языку перевода) вариант объяснения термина.

Comments

[Дмитрий]

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

[Андрей]

Значит вот тот случай, когда уже «вошел». Хотя сочетание странное и неспециалисту будет некоторым сюрпризом.