Прекратится ли этот алгоритм?

Question

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

while (curElement != average(allElements))
{
    curElement = average(allElements);
    nextElement();
}

Обратите внимание, что я предполагаю, что мы начнем заново с самого начала, если мы в концемассива.

Answer 1

Поскольку это псевдокод, простой пример с 2 элементами покажет, что существуют случаи, когда программа не завершает работу:

x = 0, y = 1;

          x     y
Step 1:   0.5   1
Step 2:   0.5   0.75
Step 3:   0.635 0.75
//and so one

С учетом математики lim(x-y) = lim( 1 / 2^n )

Значит, числа сходятся, но они никогда не равны.

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

Answer 2

Это зависит.

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

Если ваши элементы содержат значения с ограниченной точностью (например, с плавающей или двойной точностью), это займет больше времени, но ограниченное время.

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

Существует небольшая разница между вашим кодом и следующим:

var i = 1;
while (i != 0) 
    i = i / 2;

Это когда-нибудь закончится? Это действительно зависит от реализации.