|
|
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. собссно код вот он. суть оценить сложность ) я вижу только одно O(a*b) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.04.2016, 09:47 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
lor2, За счет деления на 2 в каждой итерации цикла сложность будет (a.length*ln(b.length)) Вообще, сложность проверки пересечения 2-х отсортированных списков алгоритмом слияния min(a.length,b.length). Надпись Код: java 1. будет выводиться многократно. последняя надпись Код: java 1. будет выведена всегда. Программа выглядит странно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.04.2016, 10:04 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
lor2, System.out.println требует доп. времени на вывод в консоль. Лучше будет, если закомментить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.04.2016, 10:13 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
после первого саута должен быть ретёрн просто. не берите в голову ) Марк, вопрос такой что значит мин между двух? что меньше то и будет показывать? а как вы это посчитали? респект воще. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.04.2016, 14:00 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
благодарю, но там сложность тупо посчитали как если вайл1 и вайл2 последовательно то просто сложили длину вайл 1 и вайл 2) с такой логикой если два вложенных цикла, то как раз и выходит что помножить меж собой что я с обссно и написал я конечно понимаю, что в моем случае я выкинул вообще все частности которые мне как то включить в расчет тупо мозгов не хвататет. я не пйму почему же у вас выходит минимальное значение между массивом 1 и массивом 2 (их длины)? откуда там натуральный логарифм выплывает? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.04.2016, 15:40 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
Минимальное значение - это для алгоритма, который можно написать для проверки пересечения - к приведенному никакого отношения не имеет. Логарифм - т.к. в каждой итерации цикла делится на 2. Если немного подумать, то будет понятно, что число операций будет не более, чем двоичный логарифм от размера массива. То, что там написан натуральный - для оценки производительности не принципиально - все логарифм x по двум фиксированным основаниям отличаются друг от друга на константу. Зато его можно написать в строку и его обозначение знают. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.04.2016, 17:30 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
lor2, ты нарисовал черный ящик у которого нет входа. Мы конечно можем предположить что для него входом являются два массива (причем упорядоченных) но как-то надо это объявить. И если массивы упорядоченны - то лучше наверное делать pre-check до выполнения. Или вообще отказаться от массива(вов) и передавать Set<Integer>. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.04.2016, 18:20 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
maytonlor2, ты нарисовал черный ящик у которого нет входа. Мы конечно можем предположить что для него входом являются два массива (причем упорядоченных) но как-то надо это объявить. И если массивы упорядоченны - то лучше наверное делать pre-check до выполнения. Или вообще отказаться от массива(вов) и передавать Set<Integer>. это задача - головоломка. вы ищите кота там где его нет. ) разумеется в полевых условиях только идиот будет проверять таким образом попадания между двух массивов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.04.2016, 19:12 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
lor2я вижу только одно O(a*b) имхо ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.04.2016, 19:25 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
автор (a.length*ln(b.length)) тот кто придумал эту задачку говорит что ответ неверный. как обосновать не знаю. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.04.2016, 09:43 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
lor2тот кто придумал эту задачку говорит что ответ неверный. как обосновать не знаю. Если бы понимать назначение всех этих z, f и u. Ну, вероятно, логика написана так, что условие while (z < f) всегда выдаёт больше чем N итераций. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.04.2016, 10:04 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
Blazkowiczlor2тот кто придумал эту задачку говорит что ответ неверный. как обосновать не знаю. Если бы понимать назначение всех этих z, f и u. Ну, вероятно, логика написана так, что условие while (z < f) всегда выдаёт больше чем N итераций. нет никакого назначения это по сути оленьпийская задачка. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.04.2016, 11:13 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
Usmanlor2я вижу только одно O(a*b) имхо б получается больше чем а всегда. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.04.2016, 11:26 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
кстати если каунтеры поставить то по б график на логарифм не похож. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.04.2016, 11:37 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
lor2кстати если каунтеры поставить то по б график на логарифм не похож. Ну, выходит вложенный цикл так написан, что там количество итераций не O(N), вот и всё. Что как бы не очевидно, если нет понимания алгоритма. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.04.2016, 11:52 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
Blazkowicz, что такое N? график получается практически линейный на вроде Y=X+A, где А тупо гуляет, в обе стороны на небольшое значение. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.04.2016, 12:12 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
lor2автор (a.length*ln(b.length)) тот кто придумал эту задачку говорит что ответ неверный. как обосновать не знаю. странно, в цикле бинарный поиск элементов массива a в массиве b, O(a.length*ln(b.length)) - правомочно тот кто придумал эту задачку либо сам не понял что придумал, либо какой-то хитрый подвох (что сомнительно, даже проверки краёв нет) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.04.2016, 12:12 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
lor2что такое N? Количество элементов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.04.2016, 12:16 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
пардон, значение так выглядит Y=X*A, где А изменяется по функции, ПОХОЖЕЙ на логарифм. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.04.2016, 12:20 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)....тот кто придумал эту задачку либо сам не понял ... мда... ну, сомнения нет, что так и есть. раз человек ответ не принял, значит он не понял, о чем спрашивал. и, конечно, в век ответов методом выбора элемента из списка, правильный ответ не может быть не принят, даже если отвечающий не понимает смысла произведенного выбора. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.04.2016, 12:27 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
чот я уже туплю воще туплю: простой алгоритм, двумерный массив. надо просто сумму найти всех ячеек массива. какова сложность? размер по иксу помножить на размер по игреку? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.04.2016, 13:49 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
lor2автор (a.length*ln(b.length)) тот кто придумал эту задачку говорит что ответ неверный. как обосновать не знаю. Не |a|*ln(|b|), а |a|*log2(|b|), где |b| мощность(длина) разное основание логарифма. алгоритм - поиск в сортированном массиве методом половинного деления ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.04.2016, 14:26 |
|
||
|
оценка сложности алгоритма
|
|||
|---|---|---|---|
|
#18+
Siemarglтот кто придумал эту задачку говорит что ответ неверный. как обосновать не знаю. Не |a|*ln(|b|), а |a|*log2(|b|), где |b| мощность(длина) разное основание логарифма. [/quot] Логарифмы отличаются друг от друга на КОНСТАНТУ. Поэтому O(ln(b)) = O(log_2(b)). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.04.2016, 15:37 |
|
||
|
|

start [/forum/topic.php?fid=59&msg=39208116&tid=2124179]: |
0ms |
get settings: |
10ms |
get forum list: |
19ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
65ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
79ms |
get tp. blocked users: |
2ms |
| others: | 245ms |
| total: | 435ms |

| 0 / 0 |
