Келесі кодтың жұмыс істеу уақыты қандай?

public static int Count( List lst1, List lst2)
{
    Iterator itr1 = lst1.iterator();

    int count=0;
    while ( itr1.hasNext() )
    {
        Integer x = itr1.next();
        Iterator itr2 = lst2.iterator();
        while ( itr2.hasNext() )
            if ( x.equals( itr2.next()) )
                count++;
    }

    return count;
}
  1. Егер ArrayList lst1 және lst2 үшін берілсе.
  2. Егер LinkedList lst1 және lst2 үшін берілсе.

O (n) және O (n) = O (егер O (n) ) болса, n ^ 3) . Мен дұрыс емеспін бе, жоқ па?

0
@ nachokk Шегініс егер дұрыс болса, сізге хабарлайды.
қосылды автор EJP, көзі
n = list1.size m = list2.size -> O (n * m), сіз бұл жағдайда BRACES функциясын оқылу үшін пайдалануыңыз керек
қосылды автор nachokk, көзі
@KonradRudolph шынымен? Екіншіден, ашық және аяғында тым айқын? 5 секундтан бастап бастау мен аяқталуды түсіну керек
қосылды автор nachokk, көзі
@KonradRudolph Ия, дәл қазір дұрыс идентификациямен оқуға оңай, бірақ менің айтқаным - бұл қай жерде екіншісін аяқтау керектігін анықтау.
қосылды автор nachokk, көзі
@ nachokk Мен келіспеймін. Дұрыс шегініс маңызды. Браузерлер мұнда оқылу мүмкіндігіне ешқандай рөл ойнайды; егер олар дұрыстығына ғана қатысты болса (бірақ мен басқа жерде де бұл туралы айтқанмын).
қосылды автор Konrad Rudolph, көзі
@ nachokk Мен сізге сенбеймін. Шегініс көп жақшалардан көбірек көрінеді (сондықтан дәйекті шегіну маңызды, әйтпесе неге алаңсыз?). Ешкімде Python-ді оқуға ешқандай қиындық жоқ сияқты (бірақ кейбіреулер оның оқылуына байланысты емес, бірақ оның оқылуына байланысты емес).
қосылды автор Konrad Rudolph, көзі

8 жауаптар

Бұл O (өлшемі (lst1) * өлшемі (lst2)) . lst1 ішіндегі барлық x i үшін сіз lst2 әр элементіне x i салыңыз. Бұл жағдайда Θ (мөлшері (lst1) * size (lst2)) дәл сәйкес келеді, себебі ол жоғарыда және төменде мөлшері (lst1) * өлшемімен (lst2) .

6
қосылды

Бұл O (өлшемі (lst1) * өлшемі (lst2)) . lst1 ішіндегі барлық x i үшін сіз lst2 әр элементіне x i салыңыз. Бұл жағдайда Θ (мөлшері (lst1) * size (lst2)) дәл сәйкес келеді, себебі ол жоғарыда және төменде мөлшері (lst1) * өлшемімен (lst2) .

6
қосылды

Бұл O (өлшемі (lst1) * өлшемі (lst2)) . lst1 ішіндегі барлық x i үшін сіз lst2 әр элементіне x i салыңыз. Бұл жағдайда Θ (мөлшері (lst1) * size (lst2)) дәл сәйкес келеді, себебі ол жоғарыда және төменде мөлшері (lst1) * өлшемімен (lst2) .

6
қосылды

Бұл O (өлшемі (lst1) * өлшемі (lst2)) . lst1 ішіндегі барлық x i үшін сіз lst2 әр элементіне x i салыңыз. Бұл жағдайда Θ (мөлшері (lst1) * size (lst2)) дәл сәйкес келеді, себебі ол жоғарыда және төменде мөлшері (lst1) * өлшемімен (lst2) .

6
қосылды

Күмән жоқ .. @steven жақсы математикалық өкіл берді. Мұнда жатқан үлкен О-бұл әдіске сәйкес тізімдердің өлшемдерінің көбеюі.

list1 әр элементте list2 ішіндегі әрбір элементпен салыстырылады. Осылайша, цикл SizeofList1 * SizeOfLit2 үшін жұмыс істейді.

Мұнда бастаушы нұсқаулық көмегімен Сіз оны аласыз.

0
қосылды

Күмән жоқ .. @steven жақсы математикалық өкіл берді. Мұнда жатқан үлкен О-бұл әдіске сәйкес тізімдердің өлшемдерінің көбеюі.

list1 әр элементте list2 ішіндегі әрбір элементпен салыстырылады. Осылайша, цикл SizeofList1 * SizeOfLit2 үшін жұмыс істейді.

Мұнда бастаушы нұсқаулық көмегімен Сіз оны аласыз.

0
қосылды

Күмән жоқ .. @steven жақсы математикалық өкіл берді. Мұнда жатқан үлкен О-бұл әдіске сәйкес тізімдердің өлшемдерінің көбеюі.

list1 әр элементте list2 ішіндегі әрбір элементпен салыстырылады. Осылайша, цикл SizeofList1 * SizeOfLit2 үшін жұмыс істейді.

Мұнда бастаушы нұсқаулық көмегімен Сіз оны аласыз.

0
қосылды

Күмән жоқ .. @steven жақсы математикалық өкіл берді. Мұнда жатқан үлкен О-бұл әдіске сәйкес тізімдердің өлшемдерінің көбеюі.

list1 әр элементте list2 ішіндегі әрбір элементпен салыстырылады. Осылайша, цикл SizeofList1 * SizeOfLit2 үшін жұмыс істейді.

Мұнда бастаушы нұсқаулық көмегімен Сіз оны аласыз.

0
қосылды