Твой метод оптимальнее. Извеняй, Верес, так вышло - O(logN) лучше чем O(N^2)
А как определяется когда O(logN) или O(N^2), или другое?
Дык все же очень просто.
O(1) => элементарный шаг в функции => n=1+1;
O(N) => линеарный обход => for(int i = 0; i < n; i++) {}
O(logN) => бинарный обход => for(int i = 0; i < n; i++) {if(i)}
O(N^2) => квадратный обход => for(int i = 0; i < n; i++) {for(int i = 0; i < n; i++){}}
и так далее.
Всего их 11. Всякие запредельные обходы типа факультетов и экспоненциальных в практике отсутствуют по причине долгих лет исполнения на современных компах. Кажется даже на суперкомах не дают задачи выше полимеальных и матричных инверсий. Но это все уже глухая теория.
Если есть необходимость найти оптимальный вариант, нужно смотреть на количество вероятных циклов, вложеных либо одиночных и набор условий. итоговым считается самый худший из встреченых. То есть если в методе есть бинарный и квадратный обход отдельно друг от друга, то метод оценивается как O(N^2). Но ингода есть варианты. Так лучшие алгоритмы собственно когда-то имели худший вариант решений, но потом кто-то типа Дайкстры или Кнута находит вариант получше и получает доктора.
Привет, Верес!!! Спасибо за теплые слова. Прости, что упомянул тебя. Просто Игорь обмолвился, что ты принимал участие в дискуссии, вот я и заикнулся. Надеюсь у тебя тоже все хорошо!
Игорь, спасибо за код. Сегодня смотреть не стал - зуб болит, катострофа. Завтра обязательно посмотрю.
