Büyük ilişkiler nasıl kanıtlanır

Question

Hey, başlık muhtemelen biraz kapalı, bu yüzden daha iyi nasıl koyacağınızı biliyorsanız, lütfen düzeltin. ödev aşağıdaki boyunca çok sayıda görevler verilmiş atama olarak

:

f olsun (n) ve g (n), asimptotik pozitif fonksiyonları olabilir. Aşağıdaki varsayımların her birini kanıtlayın veya onaylayın.

a. f(n) = O(g(n)) implies g(n) = O(f(n)) 

Şimdi, asıl sorum şu ki - bunu resmi bir şekilde kanıtlamak için nasıl gidiyorsunuz? Bunu kolaylaştıracağım, çünkü bunu çürütmek için karşı bir örnek verebilirdim, ama argümanın uğruna, bunun karşı örnekler olmadan bunu yapmak istediğimizi söyleyelim, tabii ki bu diğer bazı örneklerle devam ediyor. Bu işe yaramaz.

Ben şu eşitsizlikler (daha az veya eşit olması = < ile) yazdım, biraz şaşırıp

f(n) <= c1 * g(n) 
g(n) <= c2 * f(n) 

Ama tek içine bu 2 eşitsizlikleri birleştirmek nasıl belirsiz duyuyorum (in) denklemi ve onu onaylayın. Bunun çok basit bir şekilde gözden kaçtığım ve şu anda çok aptalca olduğumdan eminim - ama bunun nasıl yapılacağına dair herhangi bir işaretçi/somut örnekler harika olurdu, böylece çalışmam gerekirdi. bu soruların geri kalanı kendi başıma.

Answer 1

Neden counterexample kullanmadan bunu onaylamak istiyorsunuz? Bir iddiayı reddetmenin en doğrudan yolu budur.

Bunun yerine bunu ispat etmeniz gerekiyorsa, elbette bir counterexample kullanamazsınız. Bu durumda, contrapositive çok iyi çalışabilir - iddianın yanlış olduğunu varsayın ve bunun mantıksal bir tutarsızlığa yol açtığını gösterin.

Bu durumda, f(n) = O(g(n)) anlamına geldiğinden, f(n) <= c1 * g(n) true ile başlıyorsunuz. Şimdi, tüm f ve g için g(n) <= c2 * f(n)'un doğru olduğunu varsaymak istersiniz (bu son bölüm çok önemlidir, çünkü f ve g'u doğru şekilde seçebilirsin) ve bunun neden işe yaramayacağını göster. Sizin için ipucum: bir f ve g'u işe yaramayacak şekilde seçin ve c1 ve c2 seçiminizle çalışamayacağını gösterin.

Answer 2

Birkaç ipuçları:
f(n) = O(g(n)) bir set notation olduğunu unutmayın ve eşitsizliklerin matematiksel forma dönüştürebilirsiniz.

Basit operasyonlar sen O -notation ile yapabilirsiniz:

• f(n) = O(f(n))
• c * O(f(n)) = O(f(n)), c sabit ise
• O(f(n)) + O(f(n)) = O(f(n))
• O(O(f(n))) = O(f(n))
• O(f(n)) * O(g(n)) = O(f(n)g(n))
• O(f(n)g(n)) = f(n) * O(g(n))

(Bilgisayar Programlama Sanatı, cilt 1-O -Notation)