Ma'lumotlar tuzilmalarida orqaga qaytish algoritmi

if (res >= 0)
{
Console.WriteLine(K + " found at index: " + res);
}
else
{
Console.WriteLine(K + " not found");
}
}

private static int interpolationSearch(int[] array, int K)
{
int n = array.Length;
int low = 0;
int high = n - 1;

while (low <= high && K >= array[low] && K <= array[high])
{

int index = low + ((K - array[low]) * (high - low)) / (array[high] - array[low]);

if (array[index] < K)
{
low = index + 1;
}
else if (array[index] > K)
{
high = index - 1;
}
else
{
return index;
}
}

return -1;

}

}
Vaqt murakkabligi: O(N!) , bu erda 'N' qirolichalar soni. Birinchi ustun uchun biz "N" qatorlarni, ikkinchi ustun uchun  N-1 qatorni va hokazolarni tekshiramiz. Shuning uchun vaqt murakkabligi N * (N-1) * (N-2) ... bo'ladi. ya'ni N!

Kosmik murakkablik: O(N^2) , bu erda "N" - malikalar soni. Biz N satr va N ustun o'lchamli 2 o'lchamli massivdan foydalanamiz, shuningdek, chiziqli bo'shliqni egallaydigan rekursiya stekidan foydalanamiz.

Orqaga kuzatish algoritmi ilovalari

Orqaga qaytish algoritmlarining turli xil ilovalari mavjud . Ulardan ba'zilari quyidagilar:

Xulosa

1. 
   Backtracking - bu muammoning cheklovlarini har qanday vaqtda qondira olmaydigan echimlarni olib tashlash, bosqichma-bosqich, bir vaqtning o'zida bir bo'lakka yechim yaratishga urinish orqali muammolarni rekursiv hal qilish usuli.
   
2. 
   Orqaga qaytish texnikasi odatda bir nechta echimlar imkoniyatlari mavjud bo'lgan hollarda qo'llaniladi.
   
3. 
   Bu barcha mumkin bo'lgan echimlarni sinab ko'radigan va ulardan eng yaxshisini tanlaydigan qo'pol kuch usulidan yaxshiroqdir.