Пессимальные Алгоритмы и Анализ Вычислительной Усложнённости

[Zibx]

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

[valyard]

Или с наибольшим.

[JIghtuse]

[Zibx]

Вот slowSort на js, отлично медленно сортирует.

var slowSort = function( arr, i, j ){
    i === void 0 && (i = 0);
    j === void 0 && (j = arr.length - 1);
    var m, tmp;
    if( i >= j )
        return;
    else{
        m = ((i + j) / 2) | 0;
        slowSort( arr, i, m );
        slowSort( arr, m + 1, arr.length - 1 );
        if( arr[m] > arr[j] ){
            tmp = arr[m];
            arr[m] = arr[j];
            arr[j] = tmp;
            //console.log(m,j) //uncomment for log all swaps
        }
        slowSort( arr, i, j - 1 );
    }
}
var arr = [5,4,3,2,1,6,7,10,0];
slowSort(arr);
console.log(arr);

[grechnik]

Число сравнений в этом алгоритме [ленивого поиска research] не зависит ни от X, ни от A_i и задаётся следующей рекурсивной формулой:

Почему? В лучшем случае research(X,i,j) заканчивается после 1 сравнения и одного рекурсивного вызова research(X,i,m), то есть получается 1+T([n/2]), что сводится к Θ(log n). В худшем случае — Θ(n), но в худшем случае и наивный алгоритм справляется.

[valyard]

Приведите пример.
По сути же, алгоритм работает так: «если искомое значение где-то в первой половине, то ищем его сначала во второй». То есть, он всегда проходится по всем значениям, прежде, чем найти нужное.

[grechnik]

Прошу прощения, перепутал знак в сравнении. Если все A_i различны, вы правы.
Впрочем, если все A_i одинаковы, будет всё-таки Θ(log n), алгоритм остановится после однократного рекурсивного спуска, в какую бы сторону ни пойти.

[Killy]

Лабиринт?
Это же алгоритм обхода игровых уровней с целью собрать все ништяки и найти все секреты.
Порой приходится выбирать маршрут очень аккуратно, поскольку неожиданные кат-сцены или потраченные сюжетные предметы могут оказаться точками невозврата — и прощай ачивка в Стиме…

[valyard]

Тоже отличный пример теории (8

[valyard]

\\ не туда

[Mrrl]

Можно найти индекс элемента в массиве и вообще ничего не сравнивая:

int index(int A[],int L,int X){
  int b=0;
  for(int k=1;k<=L;k++){
     int a=(A[k-1]^X)|b;
     b|=((a|-a)>>31)&k;
  }
  return b-1;
}

Обойтись без сравнений при записи цикла, не имея прямого доступа к IP, к сожалению, не получается :( На некоторых ассемблерах это возможно.
Время — гарантированное O(L).
Я, когда увидел условие, стал искать алгоритм хотя бы за O(max(|X|,max(|A[k]|))^N), но пока ничего интересного не получилось.

Вообще, неторопливые алгоритмы проще сначала написать на брейнфаке или машине Тьюринга, а уже потом перевести на требуемый язык. А машину Тьюринга реализовать на трёх целочисленных регистрах и большом стеке возврата. Регистры, в свою очередь — на длинной арифметике, обязательно с ассемблерными вставками (учитывая, что требуются только операции inc, dec и IsZero, это несложно). Правда, памяти всё равно не хватит :(

[Mrrl]

Простой вариант поиска — вот. Ни одного сравнения! К сожалению, он разрушает массив, но и без этого можно было бы обойтись.

int index(int *A,int L,int X){
	int k,p;
	k=1;
	for(;;){
		switch(k){
		case 1: k=2-((L|-L)>>31); break;
		case 2: return -1;
		case 3: p=L-1; k=(((X>>31)|(int)((unsigned int)(-X)>>31)))+5; break;
		case 4: X++; k=7; break;
		case 5: k=8; break;
		case 6: X--; k=12; break;
		case 7: A[p]++; p--; k+=((p>>31)<<2); break;
		case 8: p=L; p--; k=9; break;
		case 9: k=11+((A[p]|-A[p])>>31); break;
		case 10: p--; k=9-((p>>31)<<1); break;
		case 11: return p;
		case 12: A[p]--; p--; k-=(p>>31); break;
		case 13: k=3; break;
		}
	}
}

[danmiru]

Цикл от -∞+1 до ∞-1 с проверкой и сохранением всех возможных ответов, с требуемой точностью.
Уж если взялись уж.

[KvanTTT]

Насколько я понимаю, такой алгоритм не вписывается в определение, так как существует алгоритм, который будет более «мудреный»:

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

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

[Mrrl]

Чтобы просто проверить, есть ли число X в массиве, достаточно построить многочлен, корнями которого являются элементы массива, а потом подставить в него X. Поскольку возможны переполнения, придётся построить несколько многочленов — по разным простым модулям, и подставить X в каждый из них. Вот только найти индекс так не получится.
Хотя можно построить второй многочлен, значения которого в корнях первого равны индексам соответствующих корней (это делается по формуле Лагранжа — но придётся следить, чтобы корни не повторялись). Тогда подставив X во второй многочлен, мы получим индекс.