Binary Search имеет сложность O (logn) .... что означает, что если есть список отсортированных элементов 'n', для поиска номера требуется сопоставление logn. Например, ваш список содержит 20 целых чисел: {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20} ... И вы хотите найти любое число в этом списке (подумайте о номере в этом списке). Теперь посмотрим на эти множества вопросов:
Q1. Is 10 the number which you chose? - (y/n)?
-------- if yes then done. (I say "No")
if no then,
Q2. Is the number less than 10 - (y/n)?
-------- I say "No"; which means the number is greater than 10
Q3. Is 15 the number which you chose? - (y/n)?
-------- if yes then done. (I say "No")
Q4. Is the number less than 15? - (y/n)?
-------- I say "Yes"; So now its sure that the number is in between 10 and 15 (i.e., [11,14])
Q5. Is 12 the number which you chose? - (y/n)?
-------- if yes then done. (I say "No")
Q6. Is the number greater than 12? - (y/n)?
I say "Yes"; So now its sure that the number is either 13 or 14
Q7. Is the number 13? - (y/n)?
-------- I say "Yes" else its 14.
(Actually I had chosen 13 as my number)
So in total there are 20 elements, log of 20 (base 2) is 4.32 ~ 4.
So here are my comparisons:
1 st comparison: Is the number less than 10 - (y/n)?
2 nd comparison: Is the number less than 15? - (y/n)?
3 rd comparison: Is the number greater than 12? - (y/n)?
4 th comparison: Is the number 13? - (y/n)?
и я найти номер 13 (или 14) всего за 4 сравнений, что справедливо, как LOGN = log20 (основание 2) = 4.
Следовательно, приложение Akinator работает следующим образом. Он работает с большим количеством данных и прогнозирует ответ на основе ответа пользователя на вопросы Акинатора. Чтение через дерево решений и дерево двоичного поиска могут помочь вам: