Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Java [игнор отключен] [закрыт для гостей] / оценка сложности алгоритма / 25 сообщений из 34, страница 1 из 2
05.04.2016, 09:47
    #39208095
lor2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
public static void main(String[] args) {

        int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int b[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        for (int apple : a) {
            int z = 0, f = b.length - 1;

            while (z < f) {

                int u = (z + f) / 2;
                if (b[u] < apple) {
                    z = u + 1;
                } else {
                    f = u;
                }
            }

            if (z != f || b[z] != apple) {
                System.out.println("b not in a");
            }
        }
        System.out.println("b cont all from a");
    }



собссно код вот он. суть оценить сложность )

я вижу только одно O(a*b)
...
Рейтинг: 0 / 0
05.04.2016, 10:04
    #39208103
Локшин Марк
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
lor2,
За счет деления на 2 в каждой итерации цикла сложность будет (a.length*ln(b.length))
Вообще, сложность проверки пересечения 2-х отсортированных списков алгоритмом слияния min(a.length,b.length).
Надпись
Код: java
1.
System.out.println("b not in a");


будет выводиться многократно.
последняя надпись
Код: java
1.
System.out.println("b cont all from a");


будет выведена всегда.
Программа выглядит странно.
...
Рейтинг: 0 / 0
05.04.2016, 10:13
    #39208116
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
lor2,

System.out.println требует доп. времени на вывод в консоль. Лучше будет, если закомментить.
...
Рейтинг: 0 / 0
05.04.2016, 14:00
    #39208378
lor2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
после первого саута должен быть ретёрн просто. не берите в голову )

Марк, вопрос такой что значит мин между двух? что меньше то и будет показывать? а как вы это посчитали? респект воще.
...
Рейтинг: 0 / 0
05.04.2016, 15:15
    #39208462
Локшин Марк
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
...
Рейтинг: 0 / 0
05.04.2016, 15:40
    #39208484
lor2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
благодарю, но там сложность тупо посчитали как если вайл1 и вайл2 последовательно то просто сложили длину вайл 1 и вайл 2) с такой логикой если два вложенных цикла, то как раз и выходит что помножить меж собой что я с обссно и написал я конечно понимаю, что в моем случае я выкинул вообще все частности которые мне как то включить в расчет тупо мозгов не хвататет. я не пйму почему же у вас выходит минимальное значение между массивом 1 и массивом 2 (их длины)? откуда там натуральный логарифм выплывает?
...
Рейтинг: 0 / 0
05.04.2016, 17:30
    #39208634
Локшин Марк
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
Минимальное значение - это для алгоритма, который можно написать для проверки пересечения - к приведенному никакого отношения не имеет.
Логарифм - т.к. в каждой итерации цикла делится на 2. Если немного подумать, то будет понятно, что число операций будет не более, чем двоичный логарифм от размера массива. То, что там написан натуральный - для оценки производительности не принципиально - все логарифм x по двум фиксированным основаниям отличаются друг от друга на константу. Зато его можно написать в строку и его обозначение знают.
...
Рейтинг: 0 / 0
05.04.2016, 18:20
    #39208679
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
lor2, ты нарисовал черный ящик у которого нет входа.
Мы конечно можем предположить что для него входом
являются два массива (причем упорядоченных) но
как-то надо это объявить.

И если массивы упорядоченны - то лучше наверное делать
pre-check до выполнения. Или вообще отказаться от массива(вов)
и передавать Set<Integer>.
...
Рейтинг: 0 / 0
05.04.2016, 19:12
    #39208721
lor2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
maytonlor2, ты нарисовал черный ящик у которого нет входа.
Мы конечно можем предположить что для него входом
являются два массива (причем упорядоченных) но
как-то надо это объявить.

И если массивы упорядоченны - то лучше наверное делать
pre-check до выполнения. Или вообще отказаться от массива(вов)
и передавать Set<Integer>.
это задача - головоломка. вы ищите кота там где его нет. ) разумеется в полевых условиях только идиот будет проверять таким образом попадания между двух массивов.
...
Рейтинг: 0 / 0
05.04.2016, 19:25
    #39208726
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
lor2я вижу только одно O(a*b)
имхо
...
Рейтинг: 0 / 0
07.04.2016, 09:43
    #39209828
lor2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
автор (a.length*ln(b.length))
тот кто придумал эту задачку говорит что ответ неверный. как обосновать не знаю.
...
Рейтинг: 0 / 0
07.04.2016, 10:04
    #39209845
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
lor2тот кто придумал эту задачку говорит что ответ неверный. как обосновать не знаю.
Если бы понимать назначение всех этих z, f и u. Ну, вероятно, логика написана так, что условие while (z < f) всегда выдаёт больше чем N итераций.
...
Рейтинг: 0 / 0
07.04.2016, 11:13
    #39209929
lor2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
Blazkowiczlor2тот кто придумал эту задачку говорит что ответ неверный. как обосновать не знаю.
Если бы понимать назначение всех этих z, f и u. Ну, вероятно, логика написана так, что условие while (z < f) всегда выдаёт больше чем N итераций.
нет никакого назначения это по сути оленьпийская задачка.
...
Рейтинг: 0 / 0
07.04.2016, 11:26
    #39209943
lor2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
Usmanlor2я вижу только одно O(a*b)
имхо
б получается больше чем а всегда.
...
Рейтинг: 0 / 0
07.04.2016, 11:37
    #39209968
lor2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
кстати если каунтеры поставить то по б график на логарифм не похож.
...
Рейтинг: 0 / 0
07.04.2016, 11:52
    #39209988
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
lor2кстати если каунтеры поставить то по б график на логарифм не похож.
Ну, выходит вложенный цикл так написан, что там количество итераций не O(N), вот и всё. Что как бы не очевидно, если нет понимания алгоритма.
...
Рейтинг: 0 / 0
07.04.2016, 12:12
    #39210016
lor2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
Blazkowicz,

что такое N? график получается практически линейный на вроде Y=X+A, где А тупо гуляет, в обе стороны на небольшое значение.
...
Рейтинг: 0 / 0
07.04.2016, 12:12
    #39210017
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
lor2автор (a.length*ln(b.length))
тот кто придумал эту задачку говорит что ответ неверный. как обосновать не знаю.
странно, в цикле бинарный поиск элементов массива a в массиве b, O(a.length*ln(b.length)) - правомочно
тот кто придумал эту задачку либо сам не понял что придумал, либо какой-то хитрый подвох (что сомнительно, даже проверки краёв нет)
...
Рейтинг: 0 / 0
07.04.2016, 12:16
    #39210022
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
lor2что такое N?

Количество элементов.
...
Рейтинг: 0 / 0
07.04.2016, 12:20
    #39210031
lor2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
пардон, значение так выглядит Y=X*A, где А изменяется по функции, ПОХОЖЕЙ на логарифм.
...
Рейтинг: 0 / 0
07.04.2016, 12:23
    #39210037
lor2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
...
Рейтинг: 0 / 0
07.04.2016, 12:27
    #39210041
booby
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
kealon(Ruslan)....тот кто придумал эту задачку либо сам не понял ...
мда...
ну, сомнения нет, что так и есть.
раз человек ответ не принял, значит он не понял, о чем спрашивал.

и, конечно, в век ответов методом выбора элемента из списка,
правильный ответ не может быть не принят, даже если отвечающий не понимает смысла произведенного выбора.
...
Рейтинг: 0 / 0
07.04.2016, 13:49
    #39210138
lor2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
чот я уже туплю воще туплю:

простой алгоритм, двумерный массив. надо просто сумму найти всех ячеек массива.

какова сложность? размер по иксу помножить на размер по игреку?
...
Рейтинг: 0 / 0
07.04.2016, 14:26
    #39210192
Siemargl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
lor2автор (a.length*ln(b.length))
тот кто придумал эту задачку говорит что ответ неверный. как обосновать не знаю.
Не |a|*ln(|b|), а |a|*log2(|b|), где |b| мощность(длина)

разное основание логарифма.
алгоритм - поиск в сортированном массиве методом половинного деления
...
Рейтинг: 0 / 0
07.04.2016, 15:37
    #39210312
Локшин Марк
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
оценка сложности алгоритма
Siemarglтот кто придумал эту задачку говорит что ответ неверный. как обосновать не знаю.
Не |a|*ln(|b|), а |a|*log2(|b|), где |b| мощность(длина)
разное основание логарифма. [/quot]
Логарифмы отличаются друг от друга на КОНСТАНТУ. Поэтому O(ln(b)) = O(log_2(b)).
...
Рейтинг: 0 / 0
Форумы / Java [игнор отключен] [закрыт для гостей] / оценка сложности алгоритма / 25 сообщений из 34, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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