алгоритмическая задачка. Найти "лишнее" за один проход

redzor

Что-то предыдущий пост не написался. Итак, есть массив чисел лонг. Там все числа разные, кроме одного, оно 2 раза повторяется. Нужно придумать однопроходный алгоритм, чтобы найти это число. Сломал уже голову в нескольких местах. Может есть, кто знает решение?

lubanj

Нужно придумать
кто поставил такую задачу? решение точно существует? или это ты сам?

Helga87

это даже не алгоритмическая задача, а просто на сообразительность. Знаний, чтобы ее решить, хватит у школьника.
подсказка для совсем ленивых: xor

vall

ты не путаешь? в баянной задаче все кроме одного повторяются.

redzor

блин, точно, я напутал. Да, все повторяются кроме одного. Я так понял, что все кругом знают решение. Ну хорошо, посижу, порадуюсь за всех.

Helga87

о! точно! =)
тест на внимательность — FAILED.
ща тоже тогда подумаю над задачкой. :)

lubanj

подобных задачек много в книге Шеня. Название книжки не помню, но там начинают с совсем тривиальных (переворот массива без дополнительной памяти) и приходят к не столь очевидным. У меня в свое время ее читать по диагонали не получалось. Кое-где после чтения условия очередной задачи, притормаживал

redzor

Круто, блин. Никогда о такой не слышал.

Bibi

если напутал, то для решения ее достаточно прочитать.
в исходной формулировке (на правах бреда, жаль, что числа у тебя long):
тебе нужна очень большая таблица простых чисел

lubanj

http://www.math.toronto.edu/dkhmelev/shen/index.html

asvsergey

Как поможет таблица простых чисел для решения этой задачи в исходной формулировке?

Bibi

их можно перемножать

lubanj

нужна очень большая таблица простых чисел
она вроде не очень большая будет
кажется даже, что простых чисел из первой полусотни хватит
апд. нет, не хватит. это только для перемножения двух лонгов

redzor

Блин, клевые там задачки.

asvsergey

Всё ранво не пойму.

Bibi

похоже, придумал что-то поумнее моего.
моя идея была в том, что можно просто на каждом шаге брать из таблицы то число, порядковый номер которого равен числу из массива и смотреть, делится ли наше индуктивное расширение на него, если нет, то умножать на него и двигаться дальше.

asvsergey

Имеется ввиду, каждому лонгу сопоставить простое число с таким порядковым номером равным значению лонга?

asvsergey

Да, понял, но потупил :)

asvsergey

Проще наверное иметь большой битовый массив :)

Bibi

foreach ( @a ) {
return $_ if $seen{ $_ };
$seen{ $_ } = 1;
}

Helga87

на каждом шаге брать из таблицы то число, порядковый номер которого равен числу из массива и смотреть, делится ли наше индуктивное расширение на него, если нет, то умножать на него и двигаться дальше.
это, конечно, формально один проход, но в реальности это хуже, чем n^2.

Marinavo_0507

> это, конечно, формально один проход
точнее это показывает, что понятие однопроходности нужно сначала определить формально
> о в реальности это хуже, чем n^2
почему хуже, если ассоциативный массив реализован деревом?

vall

правильное решение использует одну переменную типа long

Helga87

почему хуже, если ассоциативный массив реализован деревом?
посчитай сложность умножений

Helga87

точнее это показывает, что понятие однопроходности нужно сначала определить формально
поэтому обычно просят не за один проход, а за O(n). Автор темы мог попутать.
Ну, и в любом случае, нет смысла в решении за n^2, т.к. тогда работает тривиальное.

asvsergey

Можно остортировать за O(n) каким нибудь radix sort
и найти в остортированом списке за один проход. :)

Marinavo_0507

> посчитай сложность умножений
точно, не туда посмотрел

Helga87

radix sort
для long?

lubanj

ну да. именно что для лонг. хотя - для любых целых

asvsergey

А в чем проблема, формально это будет O(n правда константа будет больше чем log(n т.к. n<2^64, а в radix sort 64 прохода по массиву. n < 2^64 т.к. числа не повторяются.

Helga87

за какое время ты отсортируешь массив long-ов с помощью radix sort?

psihodog

офигеть, аутентичная ссылка...
ftp://ftp.mccme.ru/users/shen/progbook2/progbookpdf.zip

sergako

RadixSort за 4*256*O(N) вполне реальная штука. Например, для unsigned:


#define For(a, b) for(a=0; a<b; a++)



void radix_sort(unsigned int a[], int n)

{

  unsigned int *t, *a2=a;

  unsigned int *b=(unsigned int*) malloc(n*sizeof(int; 

  unsigned int *b2;

  unsigned char *bp;

  int i, j, npos, temp;

  int c[256][4];

  b2 = b;

  memset(c, 0, sizeof(int)*256*4);

  bp = (unsigned char*) a;

  For(i,n)

    For (j,4) {

      c[*bp][j]++;

      bp++;

    }

  For(j,4) {

    npos = 0;

    For(i,256) {

      temp = c[i][j];

      c[i][j] = npos;

      npos += temp;

    }

  }

  For(j,4) {	

    bp = (unsigned char*) a2 + j;

    For(i,n) {

      b[c[*bp][j]++] = a2[i];

      bp += 4;

    }

    t = a2; a2 = b; b = t;

  }

  free(b2);

}

Формально она работает за O(N но кушает O(N) памяти. В баяне ограничение по памяти было O(1).

Gaishnik

Как вам такая задача.
Есть гипотеза, что больше половины элементов массива - это один и тот же элемент.Проверить гипотезу за время O(n) и память O(1).

asvsergey

Если это числа, то можно считать биты на каждой позиции, потом определить где чего больше и составить число, за второй проход проверить сколько раз оно встречается.

danilov

почитать кол-во для каждого бита, затем полученное число проверить одним проходом.

sergako

считать количество различных соседних элементов (в т.ч. последнего с первым). если это число < N, то гипотеза верна.

asvsergey

считать количество различных соседних элементов (в т.ч. последнего с первым). если это число < N, то гипотеза верна.

Если масив будет состоять из 3-х равных частей, в каждой из которых буду одинаковые элемненты, то он не удовлетворяет гипотезе, а число переходов между соседями будт равно 3.

sergako

да, ступил.
тогда такой метод: найти медиану массива (это будет наше число, если оно есть а затем вторым проходом подсчитать кол-во элементов, не равных медиане. если это кол-во меньше N/2, то нашли число и гипотеза подтвердилась.

asvsergey

Не всегда можно найти медиану за O(n).

Marinavo_0507

поэтому обычно просят не за один проход, а за O(n). Автор темы мог попутать.
только в этой задаче O(n) формально не имеет смысла, так как n не может превосходить 2^32+1

sergako

если делать как QuickSort, то не всегда. Но можно всегда, например в этой презентации нарисовано: http://ranger.uta.edu/~gdas/Courses/Fall2004/advAlgos/studen...
так никто не делает, конечно, но можно.

SCIF32

задача с собеседования? :)

asvsergey

Странная презентация, а медиану медиан как искать?

asvsergey

По этой презентации получается не O(n) а в лучшем случае O(n * log_5(n.

smit1

точнее это показывает, что понятие однопроходности нужно сначала определить формально
й

sergako

Median of Medians algorithm гуглом ищется описание

asvsergey

из T(n) ≤ T(n/5) + T(7n/10) + O(n)
не следуте что T(n) = O(n)
а то у нас и квик сорт O(n т.к. в нем
Т(n) ≤ T(n/2) + T(n/2) + O(n)

psihodog

я так понял, намекает, что в этом алгоритме не медиана ищется, а что-то, что разбивает массив на две части, каждая из которых гарантированно не меньше какой-то части всего массива (скажем четверти). Этого достаточно, чтобы квиксорт работал гарантированно за O(n logn но это не значит, что найденное число будет медианой.

redzor

в общем, да, с собеседования. Я, правда, там год назад был, но, вот, она никак мне покоя не давала, одну в интернете потом нашел. Еще одну сам, вроде бы, решил. Но это уже потом, конечно.

asvsergey

Во обще алгоритм о поиске k-ого по порядку числа в массиве, может и будет там O(n но статья и вики этого не доказывают. А копать глубоко неохота.
Там каждый раз отсекается по какой то части массива, и ищется в оставшейся части, количество шагов зависит от n.

redzor

я бы даже сказал, что собеседование это, пожалуй, самое жесткое на моей памяти, даже пожестче гугла. Хотя конторка, вроде, нивал онлайн, клепает игрушки. А требования вон какие. 2 из 3х за час не решил - досвиданья - вот и все собеседование.

Serab

конторка нивал
Да мы уже поняли, что ты условия задач не запоминаешь, баянов не знаешь, конторку вот от нивала, оказывается, тоже отличить не можешь.

psihodog

Во обще алгоритм о поиске k-ого по порядку числа в массиве, может и будет там O(n но статья и вики этого не доказывают. А копать глубоко неохота.
Там каждый раз отсекается по какой то части массива, и ищется в оставшейся части, количество шагов зависит от n.
Видимо, всё-таки нельзя за линейное время найти k-е по порядку число, так как даже медиану нельзя найти, так как иначе не интересно было бы искать за линейное время хотя бы "приближённую медиану", т.е. медиану медиан. :) Док-ва не знаю, конечно.
А статья вики этого не доказывает, потому что это не ставит такую цель: сама медиана мало кому нужна. Важно, чтоб квиксорт гарантированно работал за O(nlogn).

psihodog

так и подумал, что это нивал =)
мне эту задачку товарищ рассказывал, который там сейчас работает, и которому давали эту задачку в том числе.
ну ладно, хорошо хоть в гугл тебя взяли, тоже в принципе ничего, хотя нивал круче, конечно. :)

redzor

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

Serab

А, хотя "Нивал Онлайн" — это может быть, конечно, не торт Нивал. Но все же, традиции должны бы сохраниться, а в Нивале они были на высоком уровне.

redzor

это не совсем тот, но, как я понял, требования к программерам и там и там жесткие

psihodog

главное, чтобы было где эти умения там применять...
а то сначала наотбирают себе, а потом сиди там пиши игровую логику, которую и школьник написать может :D

bleyman

Есть гипотеза, что больше половины элементов массива - это один и тот же элемент.Проверить гипотезу за время O(n) и память O(1)

Задачка прикольна тем, что алгоритм тривиален:


n, cnt = None, 0

for n1 in lst:

    if n1 == n: cnt += 1

    elif cnt > 0: cnt -= 1

    else: n, cnt = n1, 1

Ну и потом, если нужно не только найти число, но и проверить гипотезу, ещё раз пройти и посчитать.
А вот доказательство того, что он работает, заставляет задуматься на минутку.

Devid

Вы будете смеяться, но сегодня мне дали тестовое задание с задачей из первого поста. Ограничение по времени O(N) где N - размер массива.
Решение в треде уже есть, а то я не следил?

psihodog

Вы будете смеяться, но сегодня мне дали тестовое задание с задачей из первого поста. Ограничение по времени O(N) где N - размер массива.
Решение в треде уже есть, а то я не следил?
Тебе дали именно такую как в первом посте, или как чуть пониже там написано?
А то автор признался, что он напутал условие.

vall

решение задачи четвёртого поста в третьем

Devid

Тебе дали именно такую как в первом посте
Да, только без "однопроходности", а с O(N).

vall

если битовая длина элементов константа то его и отсортировать можно за O(N)

Devid

Не пройдет, там числа не превосходят M.

puzelena

Корректное условие ниваловской задачи такое: есть массив длины word типа word[]. Надо за один проход (именно один проход, а не О(N определить есть ли повторяющиеся элементы (если есть, то выдать значение любого из таких). Элементы массива можно портить. Размер разрешенной дополнительной памяти - константа.

danilov

Ыыыыы. У меня такая была )

Devid

Можно использовать массив, в котором могут поместиться все возможные wordы. Его размер - константа, и даже не очень большая в Windows.

agent007new

А где-нибудь в инете есть какие-нибудь ресурсы посвященные таким вот задачкам? Не топкодер и ему подобные, где задачки на алгоритмы, а именно такие головоломные задачки (иногда между ними сложно провести разницу, но думаю, что смысл понятен)?

katrin2201

projecteuler.net
но провести грань действительно сложно, там хватает и алгоритмических вещей

psihodog

это ещё другая задачка =)
мне такую давали, я даже решил :)
"за один проход" всё-таки не правильная формулировка, иначе нет смысла портить массив :)

psihodog

а вот ещё прикольная задачка, на собеседовании не решил, только по пути домой (не нивал =) ):
Дан список (указатель на голову элементы выглядят так:
struct ListElement {

  ListElement *next; // следующий элемент в списке

  ListElement *other; // какой-то другой элемент из списка

};

Надо сделать копию списка за O(n) времени.

agent007new

projecteuler.net
Я бы все-таки его отнес к разряду топкодера: там задачки все-таки из разряда тех, что можно втупую решить, правда, это будет долго считаться (хотя на эйлере обычно задачки небольшой размерности а здесь именно такая задачка, которую нужно придумать как сделать, чтобы вообще сделать. Это не столько программирование, сколько именно идейные такие вещи

katrin2201

да, там много topcoder-style вещей
но ближе к концу частенько встречаются именно идейные вещи
некоторые задачи решаются вообще с помощью только листочка бумаги

apl13

А чего тут решать-то?

Dasar

За один проход все нумеруешь
а нумерацию как и где хранишь?

apl13

Теряю.

ppplva

Супер!

ppplva

Решение(?)
 Новый список выделяется в виде массива, это дает нам N*sizeof(ListElement*) лишней памяти, т.к. последовательные ссылки в новом списке тривиальны. Дальше немного похимичить, скопировать туда-сюда ссылки исходного списка, и все получится :grin:

Dasar

Новый список выделяется в виде массива
очень хакерски, т.к. это только в низкоуровневых языках такое пройдет: ни managed-языки, ни ФЯ, ни скрипты - такое не схавают.

ppplva

Питон схавает, там списки (вроде бы) массивами хранятся. Но в таких языках вообще сложно говорить о расходе памяти - например, не очевидно, что N элементов, связанных ссылками, вразброс занимают столько же места, как и в массиве.

psihodog

> Дальше немного похимичить, скопировать туда-сюда ссылки исходного списка, и все получится
увы! даже если есть компилятор, который способен скомпилировать такой метакод,
в результате не будет копии списка :)

ppplva

А в ФЯ вообще quicksort за O(N^2) выполняется. Так что не согласен, массивы в подобных задачах имеют право на жизнь, особенно если в условии синтаксис C используется.

ppplva

Не совсем понял почему. И это совершенно честный C. На выходе будет список из тех же элементов, связанных в том же порядке, но по странному совпадению лежащими в памяти подряд.

psihodog

если ты серьёзно, то разверни "немного похимичить", а то не очень понятно...
хотя, у меня такое подозрение, что это займёт времени больше, чем решить задачу правильно :grin:
кстати, язык фиксирован: это C (ну, может C++)

Dasar

Питон схавает, там списки (вроде бы) массивами хранятся.
вот только, например, операция удаления элемента поменяется после такого хакнутого копирования.
если раньше надо было просто переставить ссылки при удалении(+вызвать free, если нет gc то теперь придется знать что есть еще массив, и с ним как-то мудрить.

psihodog

ну... ладно, согласен, может список получиться, хотя, конечно, это хакерство.
но всё равно, химия там совсем не понятная... я вот сейчас пытался представить,
как ты будешь устанавливать указатели правильно и не смог

ppplva

1. Считаем длину, выделяем массив
2. в массиве .next указывает на соответсвующий элемент исходного списка
3. в списке .next указывает на соответсвующий элемент массива
4. в массиве .other указывает на соответсвующий элемент массива (можно сделать, т.к. есть ссылки из списка на массив)
5. восстанавливаем .next в списке
6. восстанавливаем .next в массиве

katrin2201

Например так.
Первый проход - идем по оригинальному листу, и создаем два новых листа. Один из них - это будет собственно искомая копия. В копии пока заполняем только next, other оставляем пустым. Второй лист будет из ссылок other из оригинального листа. Так же на каждой итерации в конце обработки элемента из оригинального листа, присваиваем полю other в обрабатываемом элементе ссылку на элемент-копию.
Второй проход - идем по списку-копии, и по второму списку выставляем коректные other очевидным способом (cur->other->other)

ppplva

Здесь ты прав, список не совсем честный получится.
Решение с лесенкой, похоже, правильное.

psihodog

угу, по модулю массива, решение похоже на правильное.

psihodog

может поздно уже, но твоё решение я не понял...
там в оригинальном списке other в конце концов правильные будут?

Dasar

там в оригинальном списке other в конце концов правильные будут?
в этом решении, оригинальный список не модифицируется

hwh2010

в этом решении, оригинальный список не модифицируется
но требуется память на 3 списка в сумме, не так ли?

apl13

А как ФЯ схавают указатель на другой элемент списка?

Dasar

А как ФЯ схавают указатель на другой элемент списка?
а в чем отличие между указателем из C и ссылкой из других языков - кроме терминологии?

Serab

А в ФЯ вообще quicksort за O(N^2) выполняется. Так что не согласен, массивы в подобных задачах имеют право на жизнь, особенно если в условии синтаксис C используется.
Я бы скорее сказал, что в ФЯ невозможно написать qsort.

Serab

Не совсем понял почему. И это совершенно честный C. На выходе будет список из тех же элементов, связанных в том же порядке, но по странному совпадению лежащими в памяти подряд.
Фишка в том, что каждый элемент списка должен быть выделен динамически и никто не гарантирует, что 100 выделений пойдут в памяти подряд.

apl13

Я бы скорее сказал, что в ФЯ невозможно написать qsort.
Ня?

ppplva

Это read-only список :grin:

agaaaa


Краткое описание алгоритма
* выбрать элемент, называемый опорным.
* сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.
* повторить рекурсивно для «меньших» и «больших».
Под такое описание можно написать алгоритм и он будет работать за O(n log n так что вы оба неправы. :)

Serab

Напиши, пожаалуйста.

Serab

ru.wikipedia.org
Ну, кстати, приведенное определение неверно.

agaaaa

let rec qsort = function

  | [] -> []

  | pivot :: rest ->

    let lessOrEqual, greater = List.partition (fun x -> x <= pivot) rest

    qsort lessOrEqual @ (pivot :: qsort greater)

agaaaa

Дай верное со ссылкой.

Serab

Дай верное со ссылкой.
недостает отсутствия дополнительной памяти, иначе от qsort'а почти ничего и не остается =)

agaaaa

недостает отсутствия дополнительной памяти, иначе от qsort'а почти ничего и не остается =)
Ты с дубу рухнул? Там O(log n) памяти надо.
Приведённый мной вариант использует столько же памяти, сколько и времени.

Serab

В общем дело обстоит так: можно быть теоретиком от программирования и уверять, что quicksort — это выбор разделителя по некоторому (любому) правилу, разделение и рекурсивная сортировка частей.
Можно исповедовать практический подход и понять, что quicksort так назван потому что он работает бы...подождите-ка...стро! И тут уже говорить о том, что твой замечательный алгоритм, который:
1. создает тучу копий исходного массива,
2. ужасно выбирает pivot. Ну либо если его выбирать хотя бы просто из середины приводит к дополнительным O(n) операциям на каждый уровень вложенности (как в списке добраться до середины?)
3. разделяет не в лучших традициях qsort: там важно именно идти один раз по массиву, меняя элементы местами, а не создавать две выборки из исходного участка,
является quicksort'ом не приходится.
Так что все же приведенный код — это не пепси лайтquicksort.

agaaaa

Можно исповедовать практический подход и понять, что quicksort так назван потому что он работает бы...подождите-ка...стро!
То есть за O(n log n как и мой.
А всё остальное - это твои домыслы.
В оригинальном qsort не было никакого выбора элемента.

Serab

То есть за O(n log n как и мой.
нет, просто быстро, асимптотика у qsort хуже, чем у Heap Sort или MergeSort, но тем не менее, его применяют чаще. (если быть более точным, то у MergeSort есть своя большая область применения, например, именно его стоит писать в ФЯ, а не заниматься извратом).
А всё остальное - это твои домыслы.
Это не домыслы, это следствие более детальной проработки вопроса.
В оригинальном qsort не было никакого выбора элемента.
Это в каком "оригинальном"? В самом простейшем, который дает N^2 на упорядоченных массивах? У него тоже своя сфера применения: для массивов, полученных от генератора случайных чисел.
И еще: по пункту 3 что там? Пойми, все три пункта одинаково важны.

alfadred

В оригинальном qsort не было никакого выбора элемента.
Был рандомный.

Serab

Он имеет в виду qsort хоара, там все же действительно брался первый элемент. Но это очень непрактично.

Serab

Вот, например,
http://stackoverflow.com/questions/70402/why-is-quicksort-be...
вообще сайт здравый.

alfadred

Он имеет в виду qsort хоара, там все же действительно брался первый элемент. Но это очень непрактично.
Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort: Algorithm 64," Comm. ACM 4(7 321, 1961
ALGORITHM 63
PARTITION
C. A. R. HOARE
Elliott Brothers Ltd., Borehamwood, Hertfordshire, Eng.


procedure partition (A,M,N,I,J); value M,N;

            array A; integer M, N, I, J;

comment. (...)

begin

  real X; integer F;

  F : = random ( M , N ) ; X : = A[F];                  <--------------------- Вот оно

  (...)

end
ALGORITHM 64
QUICKSORT
C. A. R. HOARE
Elliott Brothers Ltd., Borehamwood, Hertfordshire, Eng.


procedure

quicksort (A,M,N); value M,N;

            array A; integer M, N;

comment. Quicksort is a very fast and convenient method of

sorting an array in the random - access store of a computer. (...)



begin

  integer I,J ;

  if M < N then begin

    partition (A,M,N,I,J);

    quicksort (A,M,J);

    quicksort (A,I,N )

  end

end

Serab

Хм, прикольно :D
Прошу прощения, так учили в школе :(
А на философии в универе всегда говорили: "читайте оригиналы", да :grin:

ppplva

Тут даже не нужно быть теоретиком, достаточно понимать, что, кроме асимптотики, у алгоритма есть еще всякие свойства: объем дополнительной памяти, cache-friendliness, устойчивость, всякие неприятные особенности (N^2 у qsort, который в предложенном функциональном варианте возникает то ли чаще, то ли в весьма нежелательных случаях). Если все это учесть, то алгоритм, похожий на qsort, в ФЯ, судя по всему, невозможен.

ppplva

Да, и nlogn памяти никуда не годится. Она, в отличии от времени, конечная.

alfadred

Хм, прикольно.
Прошу прощения, так учили в школе.
А на философии в универе всегда говорили: "читайте оригиналы", да
Просто у Кнута как основной вариант идет выбор первого элемента :)

Serab

К тому же это еще и в среднем. А так worst-case все равно N^2.
Вспомнился перл в универе. Одногруппник преподу: "Ну моя программа работает в 99.5% случаев, вот доказательство, из неравенства Чебышева. Процент легко увеличить, увеличив размер выборки."

psihodog

Видимо, всё-таки нельзя за линейное время найти k-е по порядку число, так как даже медиану нельзя найти, так как иначе не интересно было бы искать за линейное время хотя бы "приближённую медиану", т.е. медиану медиан.
Решил, всё-таки покаяться, т.к. наткнулся сейчас на это.
Можно всё-таки найти k-е по порядку число за линейное время.
Но это как раз делается через медиану медиан и недо-квиксорт.
text: http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-C...
video: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Compute...
UPD. сейчас посмотрел, в вики всё это тоже написано... походу, никто не читает ссылок :grin:

Gaishnik

Кстати, недавно где-то читал, что квиксорт с двумя пивотами и с разделением на 3 части быстрее работает.

asvsergey

Я смотрел, но меня несколько напрягает такой пункт в доказательстве (29 страница в пдф):
там рекурентная формула T(n) ≤ T(n/5) + T(3n/4) + O(n)
делается предположение, что T(n) ≤ cn
из этого выводится, что T(n) ≤ cn и следовательно сложность линейная.
Или я чего то не понимаю, или это неккоректное доказательство.

alfadred

из этого выводится, что T(n) ≤ cn и следовательно сложность линейная.Или я чего то не понимаю, или это неккоректное доказательство.
Ну, из такой рекуррентности можно вывести, что если T(n) ≤ cn для n ≤ 3N/4, то T(n) ≤ cn для n ≤ N, так что все хорошо

psihodog

ну... ээ... словосочетание "математическая индукция" тебе ни о чём не говорит? :)
или ты не про это?

asvsergey

Математическая индукция должна опираться на основание, которое доказывается отдельно, я вот про что.
То ли в в pdf неаккуратно написанно доказательство, то ли я невнимательно прочитал.

Vlad77

То ли в в pdf неаккуратно написанно доказательство
Читайте книжку лучше. Пдфка каждой своей страницей какбе намекает, какую книжку нужно читать. Глава 9, если быть точным.

psihodog

ну, там в конце такие слова: if c is chosen large enough to handle both the Θ(n) and the initial conditions.
здесь как раз "обслуживаются" две вещи:
Θ(n) — для индукционного перехода, и
initial conditions — для базы.
Оставить комментарий
Имя или ник:
Комментарий: