Saratov Linux User Group
 help / color / mirror / Atom feed
From: "Masterhard" <masterhard@cdma-saratov.ru>
To: <sarlug@lug.ru>
Subject: [Sarlug] Re: [Sarlug] [JT]Задача, помогите кому не лень
Date: Wed, 18 Sep 2002 09:16:35 +0400
Message-ID: <01b901c25ed2$910c22f0$480f930a@theundead> (raw)
In-Reply-To: <E17psoh-0006si-00@mx10.mail.ru>

А подсчитывается это так:

сложность сортировки - 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





  parent reply	other threads:[~2002-09-18  5:16 UTC|newest]

Thread overview: 5+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
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 [this message]
2002-09-18 10:29   ` [Sarlug] " Богородский Роман [Novel]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='01b901c25ed2$910c22f0$480f930a@theundead' \
    --to=masterhard@cdma-saratov.ru \
    --cc=sarlug@lug.ru \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

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