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 522
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ı?

< 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