Уведомления

Группа в Telegram: @pythonsu

#1 Янв. 31, 2015 11:27:48

fmlolka
Зарегистрирован: 2015-01-31
Сообщения: 2
Репутация: +  0  -
Профиль   Отправить e-mail  

Константный однонаправленный список

Добрый день. Необходимо выполнить следующую задачу

Найти минимальное натуральное число, отсутствующее в константном однонаправленном списке длинной N, за минимальное кол-во проходов списка. Использовать не более M дополнительной памяти.
Показать необходимое максимальное кол-во проходов списка выраженное в О-нотации.
Питон только начинаю осваивать, подскажите пожалуйста как решить эту задачу, гугл почти не помог.

Офлайн

#2 Фев. 1, 2015 00:58:07

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 9890
Репутация: +  854  -
Профиль   Отправить e-mail  

Константный однонаправленный список

O(n^2)

Начиная с единицы нужно просматривать весь список. Если единицы нет, то ответ - единица, иначе перейти к двойке и повторить. Повторять до тех пор, пока не дойдёшь до N + 1.



Отредактировано py.user.next (Фев. 1, 2015 01:00:25)

Офлайн

#3 Фев. 1, 2015 08:19:12

fmlolka
Зарегистрирован: 2015-01-31
Сообщения: 2
Репутация: +  0  -
Профиль   Отправить e-mail  

Константный однонаправленный список

Что значит O(n^2)?

Офлайн

#4 Фев. 1, 2015 10:29:42

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 9890
Репутация: +  854  -
Профиль   Отправить e-mail  

Константный однонаправленный список

fmlolka
Что значит O(n^2)?
n - количество элементов в списке
От этого количества зависит количество операций.
Если, например, в списке 1000 элементов, то количество операций будет 1000 * 1000 = 1000000.
Если, например, в списке 10000 элементов, то количество операций будет 10000 * 10000 = 100000000.



Офлайн

#5 Фев. 1, 2015 21:24:49

Alen
Зарегистрирован: 2013-08-01
Сообщения: 373
Репутация: +  49  -
Профиль   Отправить e-mail  

Константный однонаправленный список


Сложность O(n)

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from random import randint
 
class Node:
    """Описываем элемент связанного одностороннего списка.
   Параметры:
      value — значение элемента списка
      next —  указатель на следующий элемент
    """
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = next
 
def generator_link_lists(q, start, stop):
    """Генератор списка.
    Параметры:
        q — длина списка
        start — начальные значения генератора случайного натурального числа.
        stop — конечные значения генератора случайного натурального числа.
     """
    yield (Node(value=randint(start, stop), next=i) for i in range (q))
 
def find_min_value(q, start, stop):
    """Возвращает минимальное натуральное число, не входящее в
       значения связанного списка. Если такового нет, то возвращает None
    """
    link_lists = generator_link_lists(q, start, stop) # Инициализация генератора
    result = min(x.value for x in link_lists.next())
    if result > 1:
        return result - 1
    else:
        return None
 
if __name__ == '__main__':
    print(find_min_value(100000, 100, 1000000))

Офлайн

#6 Фев. 2, 2015 05:35:00

PooH
От:
Зарегистрирован: 2006-12-05
Сообщения: 1948
Репутация: +  72  -
Профиль   Отправить e-mail  

Константный однонаправленный список

Alen
Сложность O(n)
Вы напрасно создаете случайный список, потому что если бы использовали, например (1, 3, 5) то сразу бы увидели, что требуемую 2 ваш код не выдает.



Вот здесь один из первых отарков съел лаборанта. Это был такой умный отарк, что понимал даже теорию относительности. Он разговаривал с лаборантом, а потом бросился на него и загрыз…

Офлайн

#7 Фев. 2, 2015 06:08:54

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 9890
Репутация: +  854  -
Профиль   Отправить e-mail  

Константный однонаправленный список

Alen
return None
Для списка 1 2 3 4 5 должен выдать 6.



Офлайн

#8 Фев. 2, 2015 09:26:08

Alen
Зарегистрирован: 2013-08-01
Сообщения: 373
Репутация: +  49  -
Профиль   Отправить e-mail  

Константный однонаправленный список

PooH
Вы напрасно создаете случайный список, потому что если бы использовали, например (1, 3, 5) то сразу бы увидели, что требуемую 2 ваш код не выдает.

py.user.next
Для списка 1 2 3 4 5 должен выдать 6.

Ok. Я просто не правильно понял задание. Тогда действительно O(n²)

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version