Форум » Обработка числовых последовательностей » [C4] Эффективность алгоритма » Ответить

[C4] Эффективность алгоритма

tavabar: В задачах С4 требуется написать ЭФФЕКТИВНУЮ программу. По каким критериям определяется эта эффективность? Например, в задаче необходимо для получения результата выбрать числовую информацию из строки. Есть два варианта: 1) прочитать всю строку и, используя стандартные операции, функции и процедуры, выделить нужные данные и перевести в нужный формат; 2) считывая по одному символу, "добраться" до числа и прочитать его. Если взять объем используемой памяти, то первый вариант требует хранения данного строкового типа и числового, а второй - символьного и числового. Похоже, второй - эффективнее. Если взять удобство пользования программой (а это немаловажная функция), то в первом случае набираем строку, нажимаем Enter и всю работу поручаем программе, а во втором набираем после КАЖДОГО символа Enter. Значит, здесь первый способ эффективнее. Что в приоритете?

Ответов - 10

Поляков: tavabar пишет: В задачах С4 требуется написать ЭФФЕКТИВНУЮ программу. По каким критериям определяется эта эффективность? Эффективность оценивается по количеству операций и расходуемой памяти, как они зависят от размера исходных данных N (например, количества введенных чисел). Подробнее (на школьном уровне) можно почитать, например, здесь. Эффективность по памяти означает, например, что не нужно заводить массив там, где можно обойтись без массива решение с массивом, длина которого не зависит от исходных данных, лучше, чем решение, в котором все исходные данные сначала помещаются в массив решение с массивом [1..N] лучше, чем решение с массивом [1..M*N] (M > 1) решение с массивом [1..N] лучше, чем решение с матрицей [1..N,1..M] (M > 1) и т.д. Эффективность по быстродействию означает, например, что лучше получить какой-то результат без использования цикла (по формуле), чем с помощью цикла лучше решить задачу за один проход по массиву, чем за N проходов (N > 1) лучше решить задачу с помощью одного цикла (от 1 до N), чем с помощью вложенного цикла (1..N, 1..M, где M > 1) и т.д. На самом деле, часто требования эффективности по расходу памяти и по быстродействию противоречат друг другу. Это значит, что использование дополнительной памяти позволяет увеличить быстродействие и наоборот. Решение считается неэффективным, если можно увеличить быстродействие, не расходуя дополнительную память, или уменьшить объем расходуемой памяти, не снижая быстродействия.

oval: tavabar пишет: Если взять удобство пользования программой (а это немаловажная функция), то в первом случае набираем строку, нажимаем Enter и всю работу поручаем программе, а во втором набираем после КАЖДОГО символа Enter. Значит, здесь первый способ эффективнее. Что в приоритете? Тут Вы не правы, нажатие ENTER записывает всю строку во входной поток, а дальше считываем либо целиком строку, либо циклом посимвольно. После каждого символа ENTER жать не надо

tavabar: oval пишет: После каждого символа ENTER жать не надо Да, проверила, Вы правы, спасибо.


Dmitry78: С++. Использование библиотеки STL. Использование встроенных функций сортировки qsort. По сути циклы отсутствуют в написание кода, но по факту они есть в реализации функции. Каким образом будет оцениваться эффективность алгоритма.

Поляков: Dmitry78 пишет: С++. Использование библиотеки STL. Использование встроенных функций сортировки qsort. По сути циклы отсутствуют в написание кода, но по факту они есть в реализации функции. Каким образом будет оцениваться эффективность алгоритма. Судя о всему, использование STL разрешено. Постараюсь уточнить официальное мнение комиссии.

oval: Если в задаче необходима сортировка, то сортируем спокойно, а если имеется алгоритм без сортировки, то снизят балл за неэффективность. Например: для нахождения максимума сортируем массив и берем первый(последний) элемент. Но это мое мнение Поляков пишет: официальное мнение комиссии. узнать хочется.

Поляков: oval пишет: Если в задаче необходима сортировка, то сортируем спокойно, а если имеется алгоритм без сортировки, то снизят балл за неэффективность. Согласен.

Поляков: Dmitry78 пишет: С++. Использование библиотеки STL. Использование встроенных функций сортировки qsort. По сути циклы отсутствуют в написание кода, но по факту они есть в реализации функции. Каким образом будет оцениваться эффективность алгоритма. Официальный ответ: Использование STL разрешено и не является основанием для снижения оценки. Желательно также, чтобы автор ознакомился с указаниями по оцениванию в демо-версии.

Dmitry78: По поводу STL ясно. А по поводу сортировки, решение с сортировкой иногда является более "понятным", чем без нее. Хотя я в принципе понимаю, что проверяется возможность нахождения эффективного алгоритма решения задачи. С другой стороны встает вопрос о расширяемости алгоритма для решения более широкого круга задач. Найти 3 максимума (минимума) можно и без сортировки, а если нужно искать 10, 30 максимумов (минимумов)?

Поляков: Dmitry78 пишет: Найти 3 максимума (минимума) можно и без сортировки, а если нужно искать 10, 30 максимумов (минимумов)? Если вас интересует ЕГЭ, то таких задач там не будет. Если не ЕГЭ, то, по-видимому, сортировка проще и понятнее, а значит в большинстве случаев лучше.



полная версия страницы