|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
19.03.2018, 01:37 | #1 | |
Пользователь
Регистрация: 29.07.2016
Сообщений: 13
|
Нахождение момента временни, при котором radixSort начинает быстрее сортировать чем quickSort
Код:
Цитата:
Нужно найти некоторое время n0, при котором происходит смена темпа роста функций radixSort и quickSort. Известно, что quickSort имеет асимптотическйи прирост, а radixSort линейный, так как это соответственно О(logn * n) и О(n) функции. Сначала кривая QS исгибается, т.е. лежит ниже линейной, а после некоторого n0 - линейная ниже. Каким образом возможно найти это n0, например для цифр ? |
|
19.03.2018, 16:21 | #3 |
Форумчанин
Регистрация: 24.01.2011
Сообщений: 774
|
А вообще, вот тебе идея.
Мы знаем асимптотику каждого алгоритма. Ну, значит, можем найти константу C для него, просто запуская на больших n. T1 = С1*n T2 = C2*n*log(n) Мы можем приравнять: C1*n = C2*n*logn <=> C1/C2 = log n
a.k.a. Angelicos Phosphoros
Мой сайт |
20.03.2018, 01:46 | #4 |
Пользователь
Регистрация: 29.07.2016
Сообщений: 13
|
Благодраю!
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
На чем проще и быстрее написать небольшое Web-приложение? | Pavel2017 | JavaScript, Ajax | 1 | 05.01.2018 01:04 |
0.5 быстрее работает чем /2 | ts-alan | C# (си шарп) | 10 | 02.09.2015 10:33 |
Sin быстрее чем из math.h | Medved.tolik | Помощь студентам | 5 | 05.02.2012 18:40 |
Бейсик. Вычисление момента инерции,момента сопротивления площади поперечного сечения для кольца | kostia-92 | Помощь студентам | 0 | 26.06.2011 09:58 |
Помогите пожалуйста с лабами по делфи(чем быстрее, тем лучше) | Vera_Valera | Помощь студентам | 1 | 06.06.2009 10:08 |