Теория алгоритмов

@pilot12 · Регистрация: 27.10.2010

Студворк — интернет-сервис помощи студентам

Ребят как определить, какая из данных функции растет быстрее и почему?

f(n) \ g(n)
1. n − 100 \ n − 200
2. n12 \ n23
3. 100n + logn \ n + (logn)2
4. nlogn \ 10nlog10n
5. log2n \ log3n
6. 10logn \ logn2
7. n1.01 \ n(logn)2
8. n2/logn \ n(logn)2
9. n0.1 \ (log n)10

Или дайте ссылку на теорию

@Buckstabue · 29.09.2012, 15:36

Не знаю, но может стоить взять производную второго порядка и исследовать ее? Вторая производная, как раз, насколько я помню, показывает скорость изменения скорости функции

@pilot12 · 29.09.2012, 17:30 **[ТС]**

Уже разобрался, если у кого возникнут проблемы пишите- объясню. Производную брать необязательно

HighPredator · 29.09.2012, 20:39

pilot12, напишите здесь. Кому-нибудь может помочь ваше решение.

@pilot12 · 29.09.2012, 21:09 **[ТС]**

ну, например, nlogn \ 10nlog10n

все константы, которые умножаются или складываются с каким-то числом n можно отбросить, что и делаем на 1 шагу

nlogn \ nlog10n

далее расписываем логорифм произведения, как логорифм суммы

nlogn \ n(log10 + logn)

т.к логорифм можно привести к любому основанию, то log10 не играет существенной роли в росте, остается:

nlogn \ nlogn

функции одинаковы, значит растут одинаково

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@pilot12 0 / 0 / 0 Регистрация: 27.10.2010 Сообщений: 80

	Теория алгоритмов 28.09.2012, 20:44. Показов 1394. Ответов 4 Метки нет (Все метки) Ребят как определить, какая из данных функции растет быстрее и почему? f(n) \ g(n) 1. n − 100 \ n − 200 2. n12 \ n23 3. 100n + logn \ n + (logn)2 4. nlogn \ 10nlog10n 5. log2n \ log3n 6. 10logn \ logn2 7. n1.01 \ n(logn)2 8. n2/logn \ n(logn)2 9. n0.1 \ (log n)10 Или дайте ссылку на теорию 0

@Buckstabue 179 / 127 / 25 Регистрация: 12.01.2012 Сообщений: 623
	29.09.2012, 15:36
	Не знаю, но может стоить взять производную второго порядка и исследовать ее? Вторая производная, как раз, насколько я помню, показывает скорость изменения скорости функции 0

@pilot12 0 / 0 / 0 Регистрация: 27.10.2010 Сообщений: 80
	29.09.2012, 17:30 [ТС]
	Уже разобрался, если у кого возникнут проблемы пишите- объясню. Производную брать необязательно 0

HighPredator 6045 / 2160 / 753 Регистрация: 10.12.2010 Сообщений: 6,005 Записей в блоге: 3
	29.09.2012, 20:39
	pilot12, напишите здесь. Кому-нибудь может помочь ваше решение. 0

@pilot12 0 / 0 / 0 Регистрация: 27.10.2010 Сообщений: 80
	29.09.2012, 21:09 [ТС]
	ну, например, nlogn \ 10nlog10n все константы, которые умножаются или складываются с каким-то числом n можно отбросить, что и делаем на 1 шагу nlogn \ nlog10n далее расписываем логорифм произведения, как логорифм суммы nlogn \ n(log10 + logn) т.к логорифм можно привести к любому основанию, то log10 не играет существенной роли в росте, остается: nlogn \ nlogn функции одинаковы, значит растут одинаково 0