algoritma analizi

Aşağı Git Tüm Forumlar Web Tasarım - Programlama Yazılım Geliştirme Projeler algoritma analizi

Bu konudaki kullanıcılar: 1 misafir

0
Cevap 523
Tıklama 0
Öne Çıkarma

1. sayfa

algoritma analizi

Cevap Yaz

xxx1dark1xxx

12 yıl (8 mesaj)

Konu Sahibi

Question Three:
Suppose T(n)=3/2T(n/2)+n
a) Prove that T(n)=O(n) by mathematical induction (substitution).
b) Prove that T(n)=O(n) by recursive method (expansion).

Question Four:
Merge(L1, L2), below, is a function which merges two sorted linked lists L1 and L2, and outputs a single sorted linked list. By "sorted", we mean increasing order.

Merge(L1, L2)
If L1 is empty, then return L2;
If L2 is empty, then return L1;
x = the first element of L1;
y = the first element of L2;
If x<y
take out x from L1;
L = Merge(L1,L2);
Append x in the front of L;
return L;
If y<x
take out y from L2;
L = Merge(L1,L2);
Append y in the front of L;
return L;

Prove that Merge(L1, L2) runs in O(L1+L2) time.
[Hint: For a recursive algorithm, the best way is to use recurrence. Note, the Big-Oh notation should not appear in mathematical induction (substitution).]

Bu sorular hakkında yardımcı olucak var mı?

DH forumlarında vakit geçirmekten keyif alıyor gibisin ancak giriş yapmadığını görüyoruz.

Üye olduğunda özel mesaj gönderebilir, beğendiğin konuları favorilerine ekleyip takibe alabilir ve daha önce gezdiğin konulara hızlıca erişebilirsin.

Üye Ol Şimdi Değil

Bir Daha Gösterme

< Bu mesaj bu kişi tarafından değiştirildi xxx1dark1xxx -- 18 Ekim 2014; 19:52:38 >

Cevap Yaz

1. sayfa

Tüm Forumlar Web Tasarım - Programlama Yazılım Geliştirme Projeler algoritma analizi