* [Sarlug] [JT]������, �������� ���� �� ����
@ 2002-09-13 16:57 ����������� ����� [Novel]
2002-09-18 5:15 ` [Sarlug] [JT]????????, ???? ?? ???? Masterhard
` (2 more replies)
0 siblings, 3 replies; 5+ messages in thread
From: ����������� ����� [Novel] @ 2002-09-13 16:57 UTC (permalink / raw)
To: sarlug
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="us-ascii", Size: 507 bytes --]
Èìååòñÿ ñëåäóþùàÿ çàäà÷à:
"Äàí ìàññèâ èç n ýëåìåíòîâ ïðîèçâîëüíîé ïðèðîäû, òðåáóåòñÿ m ðàç âûïîëíèò ïîèñê â ýòîì ìàññèâå. Îïðåäåëèòü, ïðè êàêèõ ñîîòíîøåòíèÿõ n è m ñëåäóåò èñïîëüçîâàòü îäíó èç äâöõ ìåòîäèê :
1. Ïðÿìîé ïîèñê
2. Áèíàðíûé ïîèñê ñ óïîðÿäî÷èâàíèåì ìàññèâà."
Âîò òàêàÿ çàäà÷à. Ïî-ìîåìó îòâåò åñëè n/m>2 òîãäà 1, èíà÷å 2. Ìîæåò ýòî è íåïðàâèëüíî, íå çíàþ.  îáùåì, êàê ýòî òî÷íî ïîäñ÷èòàòü?
Best regards.
Áîãîðîäñêèé Ðîìàí [Novel]
bogorodskiy@inbox.ru
2002-09-13
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Sarlug] [JT]????????, ???? ?? ????
2002-09-13 16:57 [Sarlug] [JT]������, �������� ���� �� ���� ����������� ����� [Novel]
@ 2002-09-18 5:15 ` Masterhard
2002-09-18 5:16 ` [Sarlug] Re: [Sarlug] [JT]Задача, помогите кому не лень Masterhard
2002-09-18 5:16 ` Masterhard
2 siblings, 0 replies; 5+ messages in thread
From: Masterhard @ 2002-09-18 5:15 UTC (permalink / raw)
To: sarlug
? ?????????????? ??? ???:
????????? ?????????? - n log n
????????? ??????? ?????? - n
????????? ????????? ?????? - log n
????????????? ???????:
m * n < (n + m) log n => ?????? ????? ??? ??????????
m * n > (n + m) log n => ???????? ????? ? ???????????
----- Original Message -----
From: "??????????? ????? [Novel]" <bogorodskiy@inbox.ru>
To: <sarlug@lug.ru>
Sent: Friday, September 13, 2002 8:57 PM
Subject: [Sarlug] [JT]??????, ???????? ???? ?? ????
??????? ????????? ??????:
"??? ?????? ?? n ????????? ???????????? ???????, ????????? m ??? ????????
????? ? ???? ???????. ??????????, ??? ????? ????????????? n ? m ???????
???????????? ???? ?? ???? ??????? :
1. ?????? ?????
2. ???????? ????? ? ??????????????? ???????."
??? ????? ??????. ??-????? ????? ???? n/m>2 ????? 1, ????? 2. ????? ??? ?
???????????, ?? ????. ? ?????, ??? ??? ????? ???????????
Best regards.
??????????? ????? [Novel]
bogorodskiy@inbox.ru
2002-09-13
_______________________________________________
Sarlug mailing list
Sarlug@lug.ru
http://lug.ru/mailman/listinfo/sarlug
^ permalink raw reply [flat|nested] 5+ messages in thread
* [Sarlug] Re: [Sarlug] [JT]Задача, помогите кому не лень
2002-09-13 16:57 [Sarlug] [JT]������, �������� ���� �� ���� ����������� ����� [Novel]
2002-09-18 5:15 ` [Sarlug] [JT]????????, ???? ?? ???? Masterhard
@ 2002-09-18 5:16 ` Masterhard
2002-09-18 5:16 ` Masterhard
2 siblings, 0 replies; 5+ messages in thread
From: Masterhard @ 2002-09-18 5:16 UTC (permalink / raw)
To: sarlug
А подсчитывается это так:
сложность сортировки - n log n
сложность прямого поиска - n
сложность бинарного поиска - log n
следовательно условие:
m * n < (n + m) log n => прямой поиск без сортировки
m * n > (n + m) log n => бинарный поиск с сортировкой
----- Original Message -----
From: "Богородский Роман [Novel]" <bogorodskiy@inbox.ru>
To: <sarlug@lug.ru>
Sent: Friday, September 13, 2002 8:57 PM
Subject: [Sarlug] [JT]Задача, помогите кому не лень
Имеется следующая задача:
"Дан массив из n элементов произвольной природы, требуется m раз выполнит
поиск в этом массиве. Определить, при каких соотношетниях n и m следует
использовать одну из двцх методик :
1. Прямой поиск
2. Бинарный поиск с упорядочиванием массива."
Вот такая задача. По-моему ответ если n/m>2 тогда 1, иначе 2. Может это и
неправильно, не знаю. В общем, как это точно подсчитать?
Best regards.
Богородский Роман [Novel]
bogorodskiy@inbox.ru
2002-09-13
_______________________________________________
Sarlug mailing list
Sarlug@lug.ru
http://lug.ru/mailman/listinfo/sarlug
^ permalink raw reply [flat|nested] 5+ messages in thread
* [Sarlug] Re: [Sarlug] [JT]Задача, помогите кому не лень
2002-09-13 16:57 [Sarlug] [JT]������, �������� ���� �� ���� ����������� ����� [Novel]
2002-09-18 5:15 ` [Sarlug] [JT]????????, ???? ?? ???? Masterhard
2002-09-18 5:16 ` [Sarlug] Re: [Sarlug] [JT]Задача, помогите кому не лень Masterhard
@ 2002-09-18 5:16 ` Masterhard
2002-09-18 10:29 ` [Sarlug] " Богородский Роман [Novel]
2 siblings, 1 reply; 5+ messages in thread
From: Masterhard @ 2002-09-18 5:16 UTC (permalink / raw)
To: sarlug
А подсчитывается это так:
сложность сортировки - n log n
сложность прямого поиска - n
сложность бинарного поиска - log n
следовательно условие:
m * n < (n + m) log n => прямой поиск без сортировки
m * n > (n + m) log n => бинарный поиск с сортировкой
----- Original Message -----
From: "Богородский Роман [Novel]" <bogorodskiy@inbox.ru>
To: <sarlug@lug.ru>
Sent: Friday, September 13, 2002 8:57 PM
Subject: [Sarlug] [JT]Задача, помогите кому не лень
Имеется следующая задача:
"Дан массив из n элементов произвольной природы, требуется m раз выполнит
поиск в этом массиве. Определить, при каких соотношетниях n и m следует
использовать одну из двцх методик :
1. Прямой поиск
2. Бинарный поиск с упорядочиванием массива."
Вот такая задача. По-моему ответ если n/m>2 тогда 1, иначе 2. Может это и
неправильно, не знаю. В общем, как это точно подсчитать?
Best regards.
Богородский Роман [Novel]
bogorodskiy@inbox.ru
2002-09-13
_______________________________________________
Sarlug mailing list
Sarlug@lug.ru
http://lug.ru/mailman/listinfo/sarlug
^ permalink raw reply [flat|nested] 5+ messages in thread
* [Sarlug] Re: [Sarlug] Re: [Sarlug] [JT]Задача, помогите кому не лень
2002-09-18 5:16 ` Masterhard
@ 2002-09-18 10:29 ` Богородский Роман [Novel]
0 siblings, 0 replies; 5+ messages in thread
From: Богородский Роман [Novel] @ 2002-09-18 10:29 UTC (permalink / raw)
To: Masterhard
Hello Masterhard,
Wednesday, September 18, 2002, 9:16:35 AM, you wrote:
M> А подсчитывается это так:
M> сложность сортировки - n log n
M> сложность прямого поиска - n
M> сложность бинарного поиска - log n
M> следовательно условие:
M> m * n < (n + m) log n => прямой поиск без сортировки
m * n >> (n + m) log n => бинарный поиск с сортировкой
M> ----- Original Message -----
M> From: "Богородский Роман [Novel]" <bogorodskiy@inbox.ru>
M> To: <sarlug@lug.ru>
M> Sent: Friday, September 13, 2002 8:57 PM
M> Subject: [Sarlug] [JT]Задача, помогите кому не лень
M> Имеется следующая задача:
M> "Дан массив из n элементов произвольной природы, требуется m раз выполнит
M> поиск в этом массиве. Определить, при каких соотношетниях n и m следует
M> использовать одну из двцх методик :
M> 1. Прямой поиск
M> 2. Бинарный поиск с упорядочиванием массива."
M> Вот такая задача. По-моему ответ если n/m>2 тогда 1, иначе 2. Может это и
M> неправильно, не знаю. В общем, как это точно подсчитать?
M> Best regards.
M> Богородский Роман [Novel]
M> bogorodskiy@inbox.ru
M> 2002-09-13
M> _______________________________________________
M> Sarlug mailing list
M> Sarlug@lug.ru
M> http://lug.ru/mailman/listinfo/sarlug
M> _______________________________________________
M> Sarlug mailing list
M> Sarlug@lug.ru
M> http://lug.ru/mailman/listinfo/sarlug
ок,спасибо, но был по всей видимости глюк, письмо дошло только через 3
дня, так что уде поздно, я её решил :))
Но всё равно спасибо!
Пока!
--
Best regards,
Богородский Роман [Novel]
mailto:bogorodskiy@inbox.ru
Wednesday, September 18, 2002
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2002-09-18 10:29 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2002-09-13 16:57 [Sarlug] [JT]������, �������� ���� �� ���� ����������� ����� [Novel]
2002-09-18 5:15 ` [Sarlug] [JT]????????, ???? ?? ???? Masterhard
2002-09-18 5:16 ` [Sarlug] Re: [Sarlug] [JT]Задача, помогите кому не лень Masterhard
2002-09-18 5:16 ` Masterhard
2002-09-18 10:29 ` [Sarlug] " Богородский Роман [Novel]
Saratov Linux User Group
This inbox may be cloned and mirrored by anyone:
git clone --mirror http://lore.altlinux.org/sarlug/0 sarlug/git/0.git
# If you have public-inbox 1.1+ installed, you may
# initialize and index your mirror using the following commands:
public-inbox-init -V2 sarlug sarlug/ http://lore.altlinux.org/sarlug \
sarlug@lists.lug.ru sarlug@lug.ru
public-inbox-index sarlug
Example config snippet for mirrors.
Newsgroup available over NNTP:
nntp://lore.altlinux.org/org.altlinux.lists.sarlug
AGPL code for this site: git clone https://public-inbox.org/public-inbox.git