Hanoi Kulesi Algoritması ve 2^n Karmaşıklığı

-

Bu program, ünlü "Hanoi Kuleleri" problemini çözmek için gerekli tüm hareketleri yazdırır.
void solve_hanoi (int N, string from_peg, string to_peg, string spare_peg)
{
if (N<1) {
return;
}
if (N›1) {
solve_hanoi(N-1, from_peg, spare_peg, to_peg);
}


print “move from " + from_peg + “ to " + to_peg;
if (N›1) {
solve_hanoi(N-1, spare_peg, to_peg, from_peg);
}
}
T (N) N tane eleman için gereken süredir.
Sahibiz:
T(1) = O(1)
ve
T(N) = O(1) + 2*T(N-1) N›1 olduğu sürece
Son terimi tekrar tekrar genişletirseniz, şunları elde edersiniz:
T(N) = 3*O(1) + 4*T(N-2)
T(N) = 7*O(1) + 8*T(N-3)
...
T(N) = (2^(N-1)-1)*O(1) + (2^(N-1))*T(1)
T(N) = (2^N - 1)*O(1)
T(N) = O(2^N)
https://stackowerflow.com/questions/34915869/examp1e_of_big_o_of_2n

Yorumlar

Yorum Gönder

Bu blogdaki popüler yayınlar

Python'da Liste İçin Varyans, Standart Sapma, Ortalama, Minimum bulma, Maksimum bulma

-
01-dizi_icin_standartSapma-varyans-max-min-average In [3]: import math # karekök için def stsapma ( x1 , x2 , * y ): N = len ( y ) + 2 # Fonksiyona verilen parametre sayısı # ortalamayı hesapla toplam = x1 + x2 for z in y : toplam += z ort = toplam / N karetoplam = ( x1 - ort ) ** 2 + ( x2 - ort ) ** 2 for z in y : karetoplam += ( z - ort ) ** 2 stsap = math . sqrt ( karetoplam / ( N - 1 )) return stsap def varyans ( standartsapma ): return standartsapma * standartsapma In [7]: data = [ 1 , 2 , 2 , 3 , 3 , 3 , 3 , 4 , 4 , 5 , 5 ] s_deger = stsapma ( * data ) In [8]: v_deger = varyans ( s_deger ) In [9]: print ( "Standart Sapma: " , s_deger , " \n Varyans: " , v_deger ) Standart Sapma: 1.250454462839956 Va...
Devamı

Python'da Görüntü İşleme - Resmi Siyah Beyaz Yapma

-
Resim
# Derleyici JUPYTER -> ANACONDA 3 - Python 3 # online geliştirme yapabileceğiniz bir ortam # Kodun  arasında  boşluk varsa bu derleyici ayrı bir kutuda yazılmış anlamına gelir.  #  Buna dikkat   edelim import  matplotlib.pyplot  as  plt import  numpy  as  np from scipy.misc import imsave def convertRGB_to_GrayLevel(image_1) :     img_1=plt.imread(image_1)     img_2=np.zeros((img_1.shape[0],img_1.shape[1]))     for i in range(img_1.shape[0]):         for j in range(img_2.shape[1]):             img_2[i,j]=img_1[i,j,0]/3+img_1[i,j,1]/3+img_1[i,j,2]/3      imsave(image_1+ "_gray.jpeg" ,img_2)     plt.subplot(1,2,1)     plt.imshow(img_1)     plt.subplot(1,2,2)     plt.imshow(img_2,cmap= 'gray' )     plt.show() convertRGB_to_GrayLevel( 'widenYourWorld.jpeg'...
Devamı

Python'da Matris için Varyans, Standart Sapma, Minimum, Maximum, Ortalama değerlerini bulma

-
01-matris_icin-standarSapma-varyans-ortama-min-max In [25]: from random import randint def create_A_vector ( size ): my_vector = [] for i in range ( size ): my_vector . append ( randint ( 0 , 9 )) return my_vector def create_a_matrix ( m , n ): my_matrix = [] for i in range ( m ): my_matrix . append ( create_A_vector ( n )) return my_matrix In [26]: def maxBul ( dizi ): max = dizi [ 0 ][ 0 ] i = 1 for i in range ( len ( dizi )): for j in range ( len ( dizi [ 0 ])): if ( max < dizi [ i ][ j ]): max = dizi [ i ][ j ] return max def minBul ( dizi ): min = dizi [ 0 ][ 0 ] i = 1 for i in range ( len ( dizi )): for j in range ( len ( dizi [ 0 ])): if ( min > dizi [ i ][ j ]): min = dizi [ i ][ j ] retu...
Devamı