Каково большое время работы O следующего кода?

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

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

    return count; 
}

Если ArrayList передан для lst1 и lst2.
Если LinkedList передан для lst1 и lst2.

я иду и потому, что в то время как кулак петли O(n) затем в secong в то время как O(n) и если также O(n) = O(n^3). Я не знаю, ошибаюсь я или нет?Каково большое время работы O следующего кода?

источник

2013-06-22 jhonny alcantara

n = list1.size m = list2.size -> O (n * m), ВЫ ДОЛЖНЫ использовать BRACES в этом случае для чтения. – nachokk

@nachokk Я не согласен. Правильное углубление важно. Скобки не играют никакой роли для удобочитаемости здесь; если они вообще применимы только к правильности (но я также возражал против этого в другом месте). –

@ KonradRudolph действительно? второй, в то время как открытый и конечный слишком ясны? я должен подумать 5 секунд, чтобы понять, где начинается и заканчивается – nachokk

Это O(size(lst1)*size(lst2)). Для всех x _i в lst1 вы сравниваете x _i с каждым элементом в lst2. В этом случае это точно Θ(size(lst1)*size(lst2)), так как оно ограничено как сверху, так и снизу на size(lst1)*size(lst2).

источник

2013-06-22 22:26:10

Без сомнения .. @steven дал хорошую математическую репутацию. Здесь большое значение - умножение размеров списков, предоставляющих метод.

Поскольку каждый элемент в list1 сравнивается с каждым элементом в list2 .. Так что цикл работает для SizeofList1*SizeOfLit2.

Это beginner guide с петлями. Надеюсь, вы получите это.

источник

2013-06-22 22:31:47

Каково большое время работы O следующего кода?

ответ

Смежные вопросы