На этом форуме отвечают на конкретные вопросы. Фраза «я не понимаю, как решать» — это не вопрос. На вопрос «как решить задачу №X» вас отошлют к материалам сайта kpolyakov.spb.ru. За бессвязный поток слов и неспособность формулировать свои мысли — бан.

Если у вас не сходится ответ на какую-то задачу, пожалуйста сразу представляйте свое «правильное» решение.
Программы "заворачивайте" в тэг [pre2]...[/pre2], при этом сохраняются все отступы и применяется моноширинный шрифт. Если у вас используется сочетание "[i]" для обозначения элемента массива или строки, ставьте пробел после открывающей скобки. Иначе система выделит все дальнейшее курсивом.

Для регистрации на форуме щелкните по ссылке «Вход-регистрация» вверху страницы. В открывшееся окошко «ник» введите свою фамилию на русском языке (например, Иванов). В окошко «пароль» введите придуманный вами пароль, состоящий из латинских букв и цифр. Поставьте галочку в окошке «зарегистрироваться, я новый участник» и нажмите кнопку «ОК».

АвторСообщение
mendez



Сообщение: 6
ссылка на сообщение  Отправлено: 20.03.19 13:23. Заголовок: Эффективность по времени

Здравствуйте!
Вот текст задачи 82:
Скрытый текст

Программа, написанная мной на Python, по сути дела, проверяет все возможные пары (то есть такие, номера которых отличаются менее, чем на 5), при этом не запоминая их в общем массиве, а обрабатывая по ходу. Ниже приведен ее код. Ясно, что по памяти она эффективна, но вопрос: эффективна ли такая программа по времени? Или такой вложенный цикл, как в ней, не сказывается на эффективности?
    N=int(input()); c=0; k=[0]*5
    for i in range(N):
      x= int(input())
      for j in [k[i%5-4], k[i%5-3], k[i%5-2], k[i%5-1]]:
        if j!=0:
          if (j*x)%13==0 and (j+x)%2==1:
          c+=1
      print(k)
      k[i%5]=x
    print(c)


Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 2 [только новые]


Анна_Л



Сообщение: 16
ссылка на сообщение  Отправлено: 22.03.19 16:59. Заголовок: Вложенный цикл при л..

Вложенный цикл при любом количестве входных данных всегда рассчитан на 5 элементов, так что время обработки будет линейно возрастать с увеличением N. Такие программы вроде считаются эффективными по времени (во всяком случае, по критериям ЕГЭ)

Спасибо: 1 
ПрофильЦитата Ответить
Поляков
Администратор




Сообщение: 1846
ссылка на сообщение  Отправлено: 22.03.19 23:09. Заголовок: mendez пишет: эффект..

mendez пишет:
 цитата:
эффективна ли такая программа по времени? Или такой вложенный цикл, как в ней, не сказывается на эффективности?

Да, сложность такого алгоритма - линейная, оценивается как O(N), поэтому программа эффективна по времени. Число шагов внутреннего цикла от N не зависит.

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)		 Спасибо: 1 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума 		Все даты в формате GMT  3 час. Хитов сегодня: 476
Права: смайлы да, картинки да, шрифты нет, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет



Создай свой форум на сервисе Borda.ru
Форум находится на 3 месте в рейтинге
Текстовая версия