Big O на интервью

[Likenew]

В общем случае О(n x m), где n -число строк в векторе, m- средняя длина строки.

И как наихудший вариант при большом n : O(n^2)
Квадратическая зависимость, часто встречается при вложенных циклах и рецурсивных вызовах функций.

[IvanGrozniy]

Я и говорю, джависты программируют на С++, и хрен втолкуешь разницу между передачей параметров по значению или по ссылке. Вектора так и летают туда-сюда.

Не примите на свой счет, я о своем, наболевшем. Трудно найти C++ разработчика без Java background.

Так вы же сами горорили о копировании, а не о перемещении.

Я вижу на tech screen, что он передает параметр-массив по значению. Спрашиваю, знаком ли с концепцией O-большого, прошу написать руками копирование массива (обычный цикл с поэлементным копированием) и дать оценку (time and space complexity). Вижу, не понимает, что bi = ai не всегда O(1) операция, а просто запомнил, что если цикл на N элементов, то автоматически O(N). Не видит неявных вложенных циклов.

Типа как bead sort, который в теории O(1), а на практике фигушки.

Я вот не могу понять, вас не натаскивают на том, чтобы стереотипами не оперировать, когда людей интервьюируете? Мол, раз человек джавист, то все пропало

[8K]

Я вот не могу понять, вас не натаскивают на том, чтобы стереотипами не оперировать, когда людей интервьюируете? Мол, раз человек джавист, то все пропало

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

[fleshold]

Типа как bead sort, который в теории O(1), а на практике фигушки.

Сортировка по времени О(1)? В топку такие теории.

[8K]

Bead sort can be implemented with four general levels of complexity, among others:

O(1): The beads are all moved simultaneously in the same time unit, as would be the case with the simple physical example above. This is an abstract complexity, and cannot be implemented in practice.

[IvanGrozniy]

Ну если абстрактно, то и в О(0) можно