Bir dizgeyi ters çevirin: javascript'te yineleme vs yineleme

Question

bir ay önce bazı Google PTO üyeleri tarafından röportaj yaptım. sorulardan biri oldu: js içinde yinelemeli bir dize ters çevirin ve bu benim çözüm oldu

büyük Ç gösterimde tarafından çalışma süresini açıklamak:

function invert(s){ 
    return (s.length > 1) ? s.charAt(s.length-1)+invert(s.substring(0,s.length-1)) : s; 
} 

Oldukça basit, sanırım.

Ve büyük notasyonla ilgili olarak, hızlı bir şekilde O (n) 'yi çalışma süresi lineer olarak girişe bağlı olarak yanıtladım. - Sessizlik - ve sonra, bana sordu, eğer iterasyon ile uygularsanız, çalışma süresi açısından farklılıklar nelerdir?

Bazen derleyicinin yinelemeyi yinelemeye "çevirir" (bazı programlama dili kursu anıları), bu durumda yineleme ve özyineleme konusunda hiçbir farklılık olmadığını söylerim. Btw bu özel soruyla ilgili hiçbir geri bildirim almadığımdan ve görüşmeci “tamam” ya da “hayır” diye cevap vermediyse, belki benimle aynı fikirde olup olmadığınızı bilmek isterim ya da bana farklılıklar olup olmadığını bana açıklayabilirseniz 2 tür uygulama.

Çok teşekkürler ve Saygılar!

Answer 1

Çözümünüz bana göre O (n ²) görünüyor. substring numaralı çağrı büyük olasılıkla O'dur (n) - tipik bir uygulama yeni bir dizeye yer ayırır ve ardından alt dizeyi kopyalar. [Ama yorumlara bakın.] Dize birleştirme + muhtemelen O (n) olacaktır. Hatta length'un O (n) olması ihtimali de olabilir ama bence bu pek de olası değil.

---

Bir derleyicinin yinelemeyi yinelemeye dönüştürebileceği düşüncesini gündeme getirdiniz. Bu doğrudur, ancak işlevsel dillerin ve Şemanın dışında nadiren uygulanır; ve tipik olarak uygulanan tek dönüşüm, kuyruk yinelemesi eliminasyonu'dur. Kodunuzda, özyineleme kuyruk pozisyonunda değil: invert özyinelemeli çağrısından sonra hala + hesaplamanız gerekir. Yani kuyruk özyineleme ortadan kaldırılması sizin kodunuz için geçerli değildir. Bu, invert'un yinelemeli sürümünün farklı bir şekilde uygulanması gerektiği anlamına gelir. Bu, invert'un yinelemeli sürümünün farklı bir şekilde uygulanması gerektiği anlamına gelir. Aynı veya farklı karmaşıklığa sahip olabilir, biz onu görene kadar diyemeyiz.

Answer 2

Bir yan notta, derleyicinin yinelemenizi döngü olarak uygulamasına izin veren kuyruk özünürlüğünü kullanmak için yığında durumunuz kalmaz. Bu sorunu gidermek için size işlevine ek parametre olarak "devlet" geçirebilirsiniz: Emin değilim

function invert(sofar, s) 
{ 
    return (s.length > 0) ? invert(s.charAt(s.length-1)+sofar, s.substring(0,s.length-1)) : sofar; 
}