00:00:18.991,00:00:21.991
Минко Марков: въпроси, коментари?

00:03:58.598,00:04:01.598
Минко Марков: задачата??

00:04:18.414,00:04:21.414
Минко Марков: A[ 1  ... n] , A[i] \in {1 .. n^2}
Линейно сортиране

00:04:51.375,00:04:54.375
Минко Марков: ??

00:04:59.933,00:05:02.933
Марио Марков: Мисля си за прилагане на този метод - числата ще имат ~ln(n^2) = 2ln n цифри.. и за всяка правим линейна сортировка.. няма ли да стане n*ln n

00:05:14.448,00:05:17.448
Минко Марков: ??

00:05:17.822,00:05:20.822
Минко Марков: ??

00:05:56.562,00:05:59.562
Минко Марков: lg_2 (n^2) = 2 lg_2 (n)

00:06:21.597,00:06:24.597
Марио Марков: Да log просто по бавно се пише хаха

00:08:18.409,00:08:21.409
Марио Марков: Да

00:09:02.858,00:09:05.858
Минко Марков: ясно??

00:09:39.126,00:09:42.126
Марио Марков: Аз все още мисля, че ще стане nlogn.. защоъо всяка част има logn цифри.. и за всяка цифра сортираме с линейно време (индиректно в radix sort, използвайки quick sort)

00:12:09.691,00:12:12.691
Минко Марков: ??

00:12:19.406,00:12:22.406
Минко Марков: ??

00:12:19.438,00:12:22.438
Марио Марков: Как ще сортираме младша/старша част с counting sort? В нея отново ще имаме n^2 числа

00:12:47.272,00:12:50.272
Минко Марков: A[1 .. n]  а не A[1 .. n^2]

00:13:23.448,00:13:26.448
Марио Марков: Ааааааа и ние като ги представим двоично и ги разделим на два конкатенирани стринга, гледайки двата стринга като двоични числа те вече ще са <= n

00:13:30.114,00:13:33.114
Марио Марков: Разбрах разбрах

00:13:32.558,00:13:35.558
Марио Марков: Съжалявам мерси

00:13:50.749,00:13:53.749
Минко Марков: A[1 .. n] Ai \in {1 .. n^3}

00:14:06.513,00:14:09.513
Марио Марков: Делим на 3 стринга

00:14:22.997,00:14:25.997
Минко Марков: n^c , c = const

00:14:35.077,00:14:38.077
Минко Марков: ясно?

00:14:42.529,00:14:45.529
Марио Марков: Да

00:15:10.802,00:15:13.802
Иван Йочев: Ясно е

00:22:01.253,00:22:04.253
Минко Марков: помните защо??

00:22:15.473,00:22:18.473
Йонко Йонков: handshake lemma

00:22:15.970,00:22:18.970
Минко Марков: <= n(n-1)/2

00:22:34.380,00:22:37.380
Марио Марков: Защото това са ребрата в пълен граф

00:22:53.630,00:22:56.630
Минко Марков: m = O(n^2)

00:37:46.798,00:37:49.798
Марио Марков: Ясно, при един граф взимам c = |V|

00:40:45.907,00:40:48.907
Минко Марков: почивка до 14:15