Из домашних заданий в Массачусетском технологическом институте
Если вкратце - Снейп заставил Гарри сортировать свитки с домашними заданиями за последние 200 лет, в связи с чем у Снейпа возникла задача - как не потратить слишком много времени на проверку того, отсортированы ли свитки?)
"Harry Potter, the child wizard of Hogwarts fame, has once again run into trouble. Professor Snape has sent Harry to detention and assigned him the task of sorting all the old homework assignments from the last 200 years. Being a wizard, Harry waves his wand and says, ordinatus sortitus, and the papers rapidly pile themselves in order.
Professor Snape, however, wants to determine whether Harry’s spell correctly sorted the papers. Unfortunately, there are a large number n of papers and determining whether they are in perfect order takes W(n) time.
Professor Snape instead decides to check whether the papers are almost sorted. He wants to know whether 90% of the papers are sorted: is it possible to remove 10% of the papers and have the resulting list be sorted?"
и т.п.
Там же чуть дальше:
"On his way back from detention, Harry runs into his friend Hermione. He is upset because Professor Snape discovered that his sorting spell failed. Instead of sorting the papers correctly, each paper was within k slots of the proper position. Hermione immediately suggests that insertion sort would have easily fixed the problem. In this problem, we show that Hermione is correct (as usual)."
отсюда - http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/assignments/ps2.pdf
"Harry Potter, the child wizard of Hogwarts fame, has once again run into trouble. Professor Snape has sent Harry to detention and assigned him the task of sorting all the old homework assignments from the last 200 years. Being a wizard, Harry waves his wand and says, ordinatus sortitus, and the papers rapidly pile themselves in order.
Professor Snape, however, wants to determine whether Harry’s spell correctly sorted the papers. Unfortunately, there are a large number n of papers and determining whether they are in perfect order takes W(n) time.
Professor Snape instead decides to check whether the papers are almost sorted. He wants to know whether 90% of the papers are sorted: is it possible to remove 10% of the papers and have the resulting list be sorted?"
и т.п.
Там же чуть дальше:
"On his way back from detention, Harry runs into his friend Hermione. He is upset because Professor Snape discovered that his sorting spell failed. Instead of sorting the papers correctly, each paper was within k slots of the proper position. Hermione immediately suggests that insertion sort would have easily fixed the problem. In this problem, we show that Hermione is correct (as usual)."
отсюда - http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/assignments/ps2.pdf