kanıt n = Büyük-O (1) indüksiyonu kullanarak

Question

n = Big-O (1) ilişkisinin false olduğunu biliyorum. Fakat eğer Big-O içeren indüksiyonu kullanırsak kanıtlanabilir. Fakat yanlışlık, Big-O’yu alamayız. Ama sorum şu ki, ilişkiyi sabitleri kullanarak nasıl çürüyebiliriz.

Sahte kanıt burada, lütfen bana sabitleri kullanarak yanlış olmadığına dair kanıtı verin. Sabitlerle karışıyorum, ispatta kullanılan her ilişkinin farklı sabit mi yoksa aynı mı olduğunu bilmiyorum. Lütfen konuya ışık tutunuz.

TO prove: n= O(1) 
for n=1 , 1= O(1) proved 

indüksiyon hipotezi: bu doğrudur let: n-1 = O (1) şimdi biz bu n = O (1)

LHS : n = (n-1) + 1 
     = O(1) + 1 
     = O(1) + O(1) 
     = O(1) 

Falsely kanıtladı .. ben açıklama istiyorum kanıtlamak Yanlışlığın < = ve sabitleri, yani Big-O'nun temel tanımındadır.

Answer 1

Burada anlamanız gereken bir şey, Big-O veya basit olarak O, bir fonksiyonun büyüdüğü 'oranı' ifade etmesidir. Bu özel özelliği kanıtlamak için Matematiksel indüksiyon kullanamazsınız.

bir örneği, basit bir matematik olarak

O(n^2) = O(n^2) + O(n) 

, yukarda ifade değil O (n) = 0 anlamına gelir. Yani bunun için MI kullanmayın derim. MI mutlak değerler için daha uygundur.

Answer 2

Büyük O işareti işlevlerle ilgili olduğundan, 1 = O(1) gibi ifadelerin hiçbir anlamı yoktur. Burada kanıtladığınız şey, bir n rasgele ve f(x) = n sabit işlevini ve daha sonra f = O(1) doğru olan ve hiçbir çelişki vermemenizdir. İspatla ilgili bir sorun yok, problem f(x) = n işlevini f(n) = n işleviyle karıştırmanızdır. İkincisi için bu f = O(n) var ve eğer yöntemi ile kanıtlamaya çalışırsanız, işe yaramayacağını göreceksiniz.

Answer 3

burada gizli büyük bir mantıksal safsata yoktur: (1) fonksiyonları bir dizi

 
LHS : n = (n-1) + 1 
     = O(1) + 1 
     = O(1) + O(1) 
     = O(1) 

n bir işlev ve & Omicron olduğunu. Ne de bir sayıdır (ve indüksiyon ispatlarının hepsi, tek bir sayıdaki tek bir sayı için bir şeyi ispatlamakla ilgilidir). N = & Omicron, (1), is an informal shorthand for f ∈ Ο(1), where f(x) = x gibi eşit işaretlerin kullanılması.

Bu kanıt the fallacy of equivocation iki yollarını kullanır: eşittir işareti anlamına davranarak ziyade bütün bir fonksiyonu

daha çok sayıda (endüktif yolculuğun bir sonraki numarayı) o n edilir davranarak

• iki sayılar, yerine eleman-of

Eğer daha net bu kanıtı başarısız nedenini görmek bir işlev için başka gösterimi ile n değiştirmek istiyorsanız için bir kestirme olmanın, bir indüksiyon kanıtı ne anlama geldiğini olduğu eşittir f (burada f (x) = x), ve gerekli olduğunda işaret unsurları ile eşit işaretler ve ispatın mantıklı olup olmadığına bakın.

Temel durum:

 
let h(x) = 1 in 
      h ∈ Ο(1)  [Any function is in Ο(that function)] 

Endüktif durum: O bu bir delil bir indüksiyon olmadığını daha açık hale geldi

 
      n = (n - 1) + 1 [Algebraic identity] 
     n - 1 = n - 1  [Arithmetic] 

let f(x) = x 
    g(x) = f(x) - 1 in 
      g ∈ Ο(1)  [Assume g ∈ Ο(1) because a different function, h, was] 
      f ∈ Ο(1 + 1) [By definition of Ο] 
      f ∈ Ο(2)  [Arithmetic] 

. Bu, kendi başına geçerli bir kanıt bile değil, çünkü biz sadece ∈ & Omicron; (1), g ∈ & Omicron ile ilgisi olmadığını ispatladık; (1), çünkü bu fonksiyonlar birbirinden çok farklı davranıyor. .

Answer 4

Eğer Big-O notasyonu içeren herhangi bir zorlama işlemi yapmanız gerekiyorsa, format definition of Big-O ile başlamanız yeterlidir. Bir kanıt olarak sadece O(1) + 1 = O(1) diyemezsiniz. Kanıtı resmi tanım açısından yapmalısınız. Bir fonksiyonun (örneğin, f(n) = n) O (1) olduğunu kanıtlamak için, tanımla eşleşen benzersiz x0 ve M'yi bulmanız gerekir. Sen indüksiyon yoluyla bunu gösterebilir ve ayrıca f(n) = n olmadığını göstermek için tanımını kullanarak çelişki bir kanıt yapabilirsiniz

Olathe onun cevabını belirtildiği gibi sadece, sadece Big-O setleri ekleyemezsiniz O(1) ve fonksiyonlar. Belirli bir Big-O kümesinin bir üyesi olarak bir işlevi sınıflandıran şeyin resmi tanımıyla başlayın.