Comments 15
Боже мой, это прекрасно! Этот раздел науки даёт возможность оценить сложность самого дурного решения, соответственно можно определить те места проекта, которые можно делегировать разрабатывать другому с наименьшим ущербом.
Вот 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);
Число сравнений в этом алгоритме [ленивого поиска research] не зависит ни от X, ни от Ai и задаётся следующей рекурсивной формулой:Почему? В лучшем случае
research(X,i,j) заканчивается после 1 сравнения и одного рекурсивного вызова research(X,i,m), то есть получается 1+T([n/2]), что сводится к Θ(log n). В худшем случае — Θ(n), но в худшем случае и наивный алгоритм справляется.
Лабиринт?
Это же алгоритм обхода игровых уровней с целью собрать все ништяки и найти все секреты.
Порой приходится выбирать маршрут очень аккуратно, поскольку неожиданные кат-сцены или потраченные сюжетные предметы могут оказаться точками невозврата — и прощай ачивка в Стиме…
Это же алгоритм обхода игровых уровней с целью собрать все ништяки и найти все секреты.
Порой приходится выбирать маршрут очень аккуратно, поскольку неожиданные кат-сцены или потраченные сюжетные предметы могут оказаться точками невозврата — и прощай ачивка в Стиме…
\\ не туда
Можно найти индекс элемента в массиве и вообще ничего не сравнивая:
Обойтись без сравнений при записи цикла, не имея прямого доступа к IP, к сожалению, не получается :( На некоторых ассемблерах это возможно.
Время — гарантированное O(L).
Я, когда увидел условие, стал искать алгоритм хотя бы за O(max(|X|,max(|A[k]|))N), но пока ничего интересного не получилось.
Вообще, неторопливые алгоритмы проще сначала написать на брейнфаке или машине Тьюринга, а уже потом перевести на требуемый язык. А машину Тьюринга реализовать на трёх целочисленных регистрах и большом стеке возврата. Регистры, в свою очередь — на длинной арифметике, обязательно с ассемблерными вставками (учитывая, что требуются только операции inc, dec и IsZero, это несложно). Правда, памяти всё равно не хватит :(
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, это несложно). Правда, памяти всё равно не хватит :(
Простой вариант поиска — вот. Ни одного сравнения! К сожалению, он разрушает массив, но и без этого можно было бы обойтись.
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;
}
}
}
Цикл от -∞+1 до ∞-1 с проверкой и сохранением всех возможных ответов, с требуемой точностью.
Уж если взялись уж.
Уж если взялись уж.
Насколько я понимаю, такой алгоритм не вписывается в определение, так как существует алгоритм, который будет более «мудреный»:
А ваше идея почти то же самое, что и вставить какое-то количество очень длинных пустых циклов.
Интуитивно, неторопливый алгоритм, решающий задачу P, — это алгоритм, который впустую тратит время настолько мудрёным образом, что позволяет обмануть среднестатистического наивного наблюдателя.
А ваше идея почти то же самое, что и вставить какое-то количество очень длинных пустых циклов.
Чтобы просто проверить, есть ли число X в массиве, достаточно построить многочлен, корнями которого являются элементы массива, а потом подставить в него X. Поскольку возможны переполнения, придётся построить несколько многочленов — по разным простым модулям, и подставить X в каждый из них. Вот только найти индекс так не получится.
Хотя можно построить второй многочлен, значения которого в корнях первого равны индексам соответствующих корней (это делается по формуле Лагранжа — но придётся следить, чтобы корни не повторялись). Тогда подставив X во второй многочлен, мы получим индекс.
Хотя можно построить второй многочлен, значения которого в корнях первого равны индексам соответствующих корней (это делается по формуле Лагранжа — но придётся следить, чтобы корни не повторялись). Тогда подставив X во второй многочлен, мы получим индекс.
Sign up to leave a comment.
Пессимальные Алгоритмы и Анализ Вычислительной Усложнённости