ReSQL.ru
     
powered by simpleCommunicator - 2.0.56     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Java [игнор отключен] [закрыт для гостей] / Как считать O(n) сложнее чем O(n^2),O(n^3)
25 сообщений из 31, страница 1 из 2
  1  все
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721361
questioner
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
questioner
Гость
Мои знания ограничиваются тем, что один проход цикла это O(n), вложенный цикл это O(N^2) и так далее:

Но вот например merge sort:

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
public List<Integer> sort(List<Integer> list) {
   if (list.size() == 1) {
      return list;
   } else {
      List<Integer> leftPart = sort(list.subList(0, list.size() / 2));
      List<Integer> rightPart = sort(list.subList(list.size() / 2, list.size()));
      List<Integer> result = new ArrayList<>();
      for (int i = 0, k = 0; i + k < list.size(); ) {
         Integer leftMin = i < leftPart.size() ? leftPart.get(i) : null;
         Integer rightMin = k < rightPart.size() ? rightPart.get(k) : null;
         if (rightMin == null || (leftMin != null && leftMin < rightMin)) {
            result.add(leftMin);
            i++;
         } else {
            result.add(rightMin);
            k++;
         }
      }
      return result;
   }
}



Общеизвестно, что это O(nlogn)

n - видимо потому, что цикл. Логарифм не понимаю откуда берётся
...
Рейтинг: 0 / 0
23.10.2018, 12:23
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721362
questioner
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
questioner
Гость
questionerМои знания ограничиваются тем, что один проход цикла это O(n), вложенный цикл это O(N^2) и так далее:

Но вот например merge sort:

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
public List<Integer> sort(List<Integer> list) {
   if (list.size() == 1) {
      return list;
   } else {
      List<Integer> leftPart = sort(list.subList(0, list.size() / 2));
      List<Integer> rightPart = sort(list.subList(list.size() / 2, list.size()));
      List<Integer> result = new ArrayList<>();
      for (int i = 0, k = 0; i + k < list.size(); ) {
         Integer leftMin = i < leftPart.size() ? leftPart.get(i) : null;
         Integer rightMin = k < rightPart.size() ? rightPart.get(k) : null;
         if (rightMin == null || (leftMin != null && leftMin < rightMin)) {
            result.add(leftMin);
            i++;
         } else {
            result.add(rightMin);
            k++;
         }
      }
      return result;
   }
}



Общеизвестно, что это O(nlogn)

n - видимо потому, что цикл. Логарифм не понимаю откуда берётся

Потому, что рекурсивное дерево обходится?
...
Рейтинг: 0 / 0
23.10.2018, 12:25
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721381
andreykaT
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andreykaT
Участник
логарифм берется когда внутри цикла может быть какое-то действие которое этот цикл может укоротить. в твоем случае i и k изменяются внутри цикла. следовательно сложность логарифмическая. не будь ее - была бы эн.

кстати, могу ошибаться но в о-нотации нлогн=логн фактически. и да, нкуб тоже нет. есть нквадрат. два вложенных там у тебя цикла или двадцать два -- это не важно уже.
...
Рейтинг: 0 / 0
23.10.2018, 12:41
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721382
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
O(Log n) - поиск деленеим попалам
...
Рейтинг: 0 / 0
23.10.2018, 12:42
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721383
andreykaT
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andreykaT
Участник
есть хотя ВРОДЕ разные методы оценки комплексити я слышал про всякие вида O(a+bLogd+d2+n3) -- но по-моему меня просто на собеседовании обманули или сами дибилы верили в то что такое бывает )) Один мне доказывал что есть комплексити О(n*m) где n и m -- Это размеры каждого цикла из двух вложенных. понятия ворст кейс он по ходу тупо не знал.
...
Рейтинг: 0 / 0
23.10.2018, 12:44
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721385
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
O (омега большая) - как раз и означает ворст кейс.
...
Рейтинг: 0 / 0
23.10.2018, 12:46
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721387
andreykaT
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andreykaT
Участник
HettO (омега большая) - как раз и означает ворст кейс.
у некоторых есть заблуждение что омега - это просто некая нотация описывающая сложность алгоритма.

кстати.. если уж к казуистике спускаемся. ворст кейс хашмапа -- не 1 а n но пишут то 1? или то речь всё же о мапе в идеальном сферическом случае?
...
Рейтинг: 0 / 0
23.10.2018, 12:48
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721391
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
Я там выше опечатался, где написал О назвал омегой. Там "О".

авторкстати.. если уж к казуистике спускаемся. ворст кейс хашмапа -- не 1 а n но пишут то 1? или то речь всё же о мапе в идеальном сферическом случае?
потому что в мапу если напихать объектов с одинаковым хешем, они поместятся в один кортеж (или как он там называется не помню),
после чего алгоритм будет перебирать весь этот кортеж в поисках нужного объекта по equals - отсюда и худьшее - O(n). Лучше - Ω(1).
ИМХО.
...
Рейтинг: 0 / 0
23.10.2018, 12:52
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721393
andreykaT
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andreykaT
Участник
неее)) почему так происходит это я прекрасно знаю. я сказал это в контексте ворст кейса и описании комплексити. так, т.е. есть О нотация есть Омега нотация для хашмапа О нотация всё же не ворст кейс показывает?
...
Рейтинг: 0 / 0
23.10.2018, 12:54
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721395
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
На википендии написано что у хешмепа среднее - О(1), худьшее - О(n)
По поводу омеги, тетты и других букв, читал где-то давно в статье какой-то, но видимо мало кто использует эти буквы.
...
Рейтинг: 0 / 0
23.10.2018, 12:55
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721403
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
автор О нотация всё же не ворст кейс показывает

Русской версии википедии - получается что О - это именно худьшее.
https://ru.wikipedia.org/wiki/Вычислительная_сложность


В английской почему-то я не нашел дополнительных букв и там пишут просто best/average/worst case.
https://en.wikipedia.org/wiki/Computational_complexity_theory#Best,_worst_and_average_case_complexity
...
Рейтинг: 0 / 0
23.10.2018, 13:02
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721470
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
"О-большое" это не худшее и не лучшее.
Это "оценка по порядку величины".
...
Рейтинг: 0 / 0
23.10.2018, 14:37
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721524
questioner
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
questioner
Гость
andreykaTлогарифм берется когда внутри цикла может быть какое-то действие которое этот цикл может укоротить. в твоем случае i и k изменяются внутри цикла. следовательно сложность логарифмическая. не будь ее - была бы эн.

кстати, могу ошибаться но в о-нотации нлогн=логн фактически. и да, нкуб тоже нет. есть нквадрат. два вложенных там у тебя цикла или двадцать два -- это не важно уже.

Ну ты чего то совсем гонишь
...
Рейтинг: 0 / 0
23.10.2018, 15:59
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721611
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
questioner, вы уверены что правильно скопировали исходник?
...
Рейтинг: 0 / 0
23.10.2018, 18:16
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721624
questioner
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
questioner
Гость
maytonquestioner, вы уверены что правильно скопировали исходник?
Я не копировал - сам написал.

Пару кейсов прошло. А что накосячил где?
...
Рейтинг: 0 / 0
23.10.2018, 18:31
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721627
andreykaT
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andreykaT
Участник
questionerandreykaTлогарифм берется когда внутри цикла может быть какое-то действие которое этот цикл может укоротить. в твоем случае i и k изменяются внутри цикла. следовательно сложность логарифмическая. не будь ее - была бы эн.

кстати, могу ошибаться но в о-нотации нлогн=логн фактически. и да, нкуб тоже нет. есть нквадрат. два вложенных там у тебя цикла или двадцать два -- это не важно уже.

Ну ты чего то совсем гонишь
конкретизируй предъявы.
...
Рейтинг: 0 / 0
23.10.2018, 18:34
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721628
questioner
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
questioner
Гость
andreykaTлогарифм берется когда внутри цикла может быть какое-то действие которое этот цикл может укоротить. в твоем случае i и k изменяются внутри цикла. следовательно сложность логарифмическая. не будь ее - была бы эн.

кстати, могу ошибаться но в о-нотации нлогн=логн фактически. и да, нкуб тоже нет. есть нквадрат. два вложенных там у тебя цикла или двадцать два -- это не важно уже.

Ну при insertion sort вложенный цикл уменьшается и всё равно n^2
...
Рейтинг: 0 / 0
23.10.2018, 18:39
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721629
andreykaT
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andreykaT
Участник
код покажи
...
Рейтинг: 0 / 0
23.10.2018, 18:39
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721630
andreykaT
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andreykaT
Участник
...посмотрел. там два вложенных цикла. где противоречие со сказанным мною??
...
Рейтинг: 0 / 0
23.10.2018, 18:40
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721631
questioner
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
questioner
Гость
andreykaTесть хотя ВРОДЕ разные методы оценки комплексити я слышал про всякие вида O(a+bLogd+d2+n3) -- но по-моему меня просто на собеседовании обманули или сами дибилы верили в то что такое бывает )) Один мне доказывал что есть комплексити О(n*m) где n и m -- Это размеры каждого цикла из двух вложенных. понятия ворст кейс он по ходу тупо не знал.

Вообще-то может. вот пример O(n+m) - https://ru.wikipedia.org/wiki/Сортировка_подсчётом
...
Рейтинг: 0 / 0
23.10.2018, 18:41
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721632
questioner
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
questioner
Гость
andreykaT...посмотрел. там два вложенных цикла. где противоречие со сказанным мною??

andreykaT логарифм берется когда внутри цикла может быть какое-то действие которое этот цикл может укоротить.
...
Рейтинг: 0 / 0
23.10.2018, 18:42
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721635
andreykaT
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andreykaT
Участник
questionerandreykaTесть хотя ВРОДЕ разные методы оценки комплексити я слышал про всякие вида O(a+bLogd+d2+n3) -- но по-моему меня просто на собеседовании обманули или сами дибилы верили в то что такое бывает )) Один мне доказывал что есть комплексити О(n*m) где n и m -- Это размеры каждого цикла из двух вложенных. понятия ворст кейс он по ходу тупо не знал.

Вообще-то может. вот пример O(n+m) - https://ru.wikipedia.org/wiki/Сортировка_подсчётом
ты хоть читаешь то что сюда линками выкладываешь? где ты там О нотацию вообще увидел?
...
Рейтинг: 0 / 0
23.10.2018, 18:51
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721637
questioner
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
questioner
Гость
andreykaTquestionerпропущено...


Вообще-то может. вот пример O(n+m) - https://ru.wikipedia.org/wiki/Сортировка_подсчётом
ты хоть читаешь то что сюда линками выкладываешь? где ты там О нотацию вообще увидел?

https://en.wikipedia.org/wiki/Counting_sort Therefore, the time for the whole algorithm is the sum of the times for these steps, O(n + k).
...
Рейтинг: 0 / 0
23.10.2018, 18:57
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721639
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
questionermaytonquestioner, вы уверены что правильно скопировали исходник?
Я не копировал - сам написал.

Пару кейсов прошло. А что накосячил где?
Я не говорил что ты накосячил.

Главная задача которая ставилась теоретиками перед merge sort - это сортировка последовательных данных. Лент. Дисковых файлов. Причем - многократно превышающих доступную память.

У тебя эти фичи не показаны. И не продемонстрирована работа со стримами.

Кроме того имеют место различные операции с массивами. Я бы их попробовал избежать.
...
Рейтинг: 0 / 0
23.10.2018, 18:59
| Ответить | Цитировать | Написать  
Как считать O(n) сложнее чем O(n^2),O(n^3)
    #39721641
andreykaT
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andreykaT
Участник
questionerandreykaTпропущено...

ты хоть читаешь то что сюда линками выкладываешь? где ты там О нотацию вообще увидел?

https://en.wikipedia.org/wiki/Counting_sort Therefore, the time for the whole algorithm is the sum of the times for these steps, O(n + k).
у тебя в двух линках написано по-разному. мне какой больше верить?
...
Рейтинг: 0 / 0
23.10.2018, 19:02
| Ответить | Цитировать | Написать  
25 сообщений из 31, страница 1 из 2
  1  все
Форумы / Java [игнор отключен] [закрыт для гостей] / Как считать O(n) сложнее чем O(n^2),O(n^3)
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=59&msg=39721383&tid=2121696]:
 0ms
get settings:
 9ms
get forum list:
 15ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 58ms
get topic data:
 9ms
get forum data:
 3ms
get page messages:
 59ms
get tp. blocked users:
 1ms
others: 325ms
total:  487ms
созд. / загр.: 487ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]