Отправлено: 05.03.12 14:48. Заголовок: [C4] Эффективность алгоритма

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

 Отправлено: 05.03.12 18:03. Заголовок: tavabar пишет: В зад..

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)

и т.д.

На самом деле, часто требования эффективности по расходу памяти и по быстродействию противоречат друг другу. Это значит, что использование дополнительной памяти позволяет увеличить быстродействие и наоборот.

Решение считается неэффективным, если можно увеличить быстродействие, не расходуя дополнительную память, или уменьшить объем расходуемой памяти, не снижая быстродействия.

 Отправлено: 06.03.12 11:24. Заголовок: tavabar пишет: Если..

tavabar пишет:

цитата:

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

Тут Вы не правы, нажатие ENTER записывает всю строку во входной поток, а дальше считываем либо целиком строку, либо циклом посимвольно. После каждого символа ENTER жать не надо

 Отправлено: 06.03.12 14:02. Заголовок: oval пишет: После к..

oval пишет:

цитата:

После каждого символа ENTER жать не надо

Да, проверила, Вы правы, спасибо.

 Отправлено: 16.03.12 11:13. Заголовок: К вопросу об эффективности алгоритма

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

 Отправлено: 16.03.12 13:22. Заголовок: Dmitry78 пишет: С++...

Dmitry78 пишет:

цитата:

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

Судя о всему, использование STL разрешено. Постараюсь уточнить официальное мнение комиссии.

 Отправлено: 16.03.12 15:31. Заголовок: Если в задаче необхо..

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

цитата:

официальное мнение комиссии.

узнать хочется.

 Отправлено: 16.03.12 15:36. Заголовок: oval пишет: Если в з..

oval пишет:

цитата:

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

Согласен.

 Отправлено: 16.03.12 17:16. Заголовок: Dmitry78 пишет: С++...

Dmitry78 пишет:

цитата:

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

Официальный ответ:

цитата:

Использование STL разрешено и не является основанием для снижения оценки. Желательно также, чтобы автор ознакомился с указаниями по оцениванию в демо-версии.

 Отправлено: 16.03.12 19:34. Заголовок: Спасибо за ответ.

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

 Отправлено: 16.03.12 20:03. Заголовок: Dmitry78 пишет: Найт..

Dmitry78 пишет:

цитата:

Найти 3 максимума (минимума) можно и без сортировки, а если нужно искать 10, 30 максимумов (минимумов)?

Если вас интересует ЕГЭ, то таких задач там не будет. Если не ЕГЭ, то, по-видимому, сортировка проще и понятнее, а значит в большинстве случаев лучше.