天天看喪氣話再膳，搞得整個(gè)人都喪了禾嫉，那個(gè)令人喪氣的文章就在下面
引文：字節(jié)跳動(dòng)——面試by民工哥技術(shù)之路
作為年輕人，不管去哪面軟件，總是有公司愛(ài)問(wèn)算法，真是讓人腦殼疼膀捷。想了想當(dāng)初大學(xué)里自己算法也算是系統(tǒng)學(xué)習(xí)考試過(guò)迈嘹，該拿出來(lái)裝裝逼了（復(fù)習(xí)一下）。
算法的基礎(chǔ)就不在這里詳述了（雖然其實(shí)算法很多概念有詳細(xì)理念）全庸，開(kāi)始Ｐ阒佟（備注：本系列語(yǔ)言不限，你有可能看到python壶笼？c++神僵？c#？java?甚至shell?js?因?yàn)樗惴ㄊ腔A(chǔ)胁赢，語(yǔ)言不應(yīng)該是限制算法的理由吹害，雖然肯定是用c算法效率最高谓媒。。恃轩。）
用數(shù)學(xué)的思想解析算法題
小時(shí)候结洼，數(shù)學(xué)大題正常有三種：證明題、計(jì)算題叉跛、應(yīng)用題松忍。當(dāng)然還有個(gè)幾何題，不過(guò)這個(gè)有點(diǎn)高深筷厘，不混為一談了挽铁。算法也是這樣，連難度都有點(diǎn)類似：應(yīng)用題>=證明題>計(jì)算題敞掘。有很多人可能認(rèn)為，證明題應(yīng)該比應(yīng)用題難伴固玖雁？想想那時(shí)候，最后一題都是證明題盖腕，難爆了赫冬，每次只能做一小問(wèn)浓镜，ε=(′ο｀*)))唉。針對(duì)這個(gè)觀點(diǎn)劲厌，只能說(shuō)膛薛，小伙子（美女！）补鼻，現(xiàn)實(shí)永遠(yuǎn)比想象復(fù)雜多了哄啄。從開(kāi)始從事算法有關(guān)開(kāi)始，就是一個(gè)對(duì)現(xiàn)實(shí)生活建模的開(kāi)始（有些牛逼的公司已經(jīng)開(kāi)始用模型來(lái)自動(dòng)建模了７绶丁）咨跌，成功的建模在常見(jiàn)的兩樣現(xiàn)代技術(shù)中十分常見(jiàn)：第一，大數(shù)據(jù)的篩選硼婿、分析锌半、推舉；第二寇漫，機(jī)器學(xué)習(xí)的監(jiān)督式學(xué)習(xí)刊殉、非監(jiān)督式學(xué)習(xí)、增強(qiáng)學(xué)習(xí)州胳。之所以所機(jī)器比人更可靠记焊，正是因?yàn)槿缃竦臋C(jī)器仍然逃不開(kāi)模型輸入和輸出的概念，也正是如此先把自己的機(jī)器人恐慌癥放到一邊吧陋葡！O(∩_∩)O哈哈~
第一題：遞歸OR循環(huán)亚亲？
說(shuō)到算法，最可怕的一題就是斐波那契數(shù)列了（不是新手噩夢(mèng)動(dòng)態(tài)規(guī)劃８汀０乒椤！）岭粤，說(shuō)這個(gè)之前惜索，我們先看個(gè)簡(jiǎn)單的：
什么你說(shuō)太簡(jiǎn)單了，給把這個(gè)人拖出去打死
遞歸和循環(huán)滿足的條件數(shù)學(xué)意義上一定滿足類似如下這種形式剃浇，數(shù)學(xué)上一般叫做數(shù)學(xué)歸納法巾兆。
即后一項(xiàng)n一定程度上與前一項(xiàng)n-1或者前幾項(xiàng)n-1,n-2......有一定邏輯上的遞歸關(guān)系，所以斐波那契數(shù)列我們也可以歸納如下的遞歸關(guān)系：
求問(wèn)用遞歸寫(xiě)斐波那契數(shù)列的難度降低了多少虎囚？不說(shuō)難度零星繼續(xù)拖出角塑！遞歸的難點(diǎn)完全集中在規(guī)律的歸納上面，以后有可能看些難的淘讥。
#/usr/bin/python
def count_sd(ass):
if ass > 2:
return count_sd(ass-1) + count_sd(ass-2)
else:
return 1
number = 10
print(count_sd(number))
#55
#[Finished in 0.1s]
#1,1,2,3,5,8,13,21,34,55
說(shuō)圃伶！大膽的說(shuō)出來(lái)，真的！真的好簡(jiǎn)單窒朋！
好搀罢！對(duì)不起，用遞歸寫(xiě)斐波那契數(shù)列先扣五分侥猩。此處備注一條極難考試題榔至，作者也不知道答案：用遞歸寫(xiě)斐波那契數(shù)列算法的空間復(fù)雜度(2^n)和時(shí)間復(fù)雜度(n)。
如上圖所示欺劳，假設(shè)我們要算第五個(gè)斐波那契數(shù)列唧取，我們莫名其妙的算過(guò)兩次第三個(gè)斐波那契數(shù)列的值，不得不說(shuō)這是一種對(duì)效能的極大浪費(fèi)（同時(shí)也會(huì)去炸運(yùn)存杰标，因?yàn)檫f歸的特殊性兵怯。遞歸的上一層f(n)是被壓棧了，要等f(wàn)(n-1)和f(n-2)運(yùn)算出來(lái)腔剂，才會(huì)把f(n)占用的內(nèi)存空間釋放出來(lái)媒区，如果層數(shù)過(guò)多，可能會(huì)掸犬，嘖嘖嘖袜漩。打住，頂多報(bào)錯(cuò)嗎）湾碎，這兩種問(wèn)題直接給遞歸打上了勁看不禁用的標(biāo)簽宙攻，但是遞歸的簡(jiǎn)單還是在只涉及f(n)與f(n-1)關(guān)系有著很大的應(yīng)用。
補(bǔ)充：其實(shí)是有優(yōu)化空間的介褥，而重點(diǎn)就是把原來(lái)遞歸的一化二座掘，改為一化一，并且借助編譯器自身的優(yōu)化能力(教訓(xùn)：python編譯器默認(rèn)沒(méi)有此類優(yōu)化)柔滔，彌補(bǔ)此上的兩種缺陷溢陪，那就是尾遞歸：
#/usr/bin/c#
#c++還沒(méi)裝好。睛廊。形真。連用兩個(gè)c#
using System;
namespace ConsoleApp1
{
/*邏輯是啥？第三個(gè)數(shù)字等于第二個(gè)數(shù)字加上第一個(gè)數(shù)字
*用n來(lái)記錄循環(huán)的次數(shù)
*用另外兩個(gè)參數(shù)記錄f(n)和f(n-1)的值
*此時(shí)其實(shí)可以發(fā)現(xiàn)超全，計(jì)算過(guò)程正過(guò)來(lái)了咆霜，不像原來(lái)的遞歸從f(n)開(kāi)始計(jì)算了，而是先retrun Fib(1,2,5),再return Fib(2,3,4),一直遞歸下去嘶朱。大多數(shù)語(yǔ)言對(duì)尾遞歸的優(yōu)化也是基于這一點(diǎn)：上一層遞歸return的值是已知狀態(tài)蛾坯，就不需要保存上一層的狀態(tài)了，釋放了堆棧的壓力(其實(shí)就是變成循環(huán)了疏遏。偿衰。挂疆。)。
*尾遞歸可以參照如下的優(yōu)化方式：比如遞歸sum(n) = f(n) = f(n-1) + value(n) ;而使用尾遞歸f(n, sum) = f(n-1, sum+value(n));
*/
class Program
{
static void Main(string[] args)
{
int n = 6;
long ret = Fib(1, 1, n);
Console.WriteLine("Hello World!"+ ret);
Console.ReadKey();
}
static long Fib(long first, long second, long n)
{
if (n < 3)
return second;
return Fib(second, second+first,n-1);
}
}
}
尾遞歸函數(shù)是指函數(shù)的最后一個(gè)動(dòng)作是調(diào)用函數(shù)本身的遞歸函數(shù)(習(xí)題：階乘轉(zhuǎn)化為尾遞歸)
可以下翎，既然遞歸陣亡了，讓循環(huán)上場(chǎng)吧
#/usr/bin/c#
using System;
namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
int n = 6;
long ret = Fib(1, 1, n);
Console.WriteLine("Hello World!"+ ret);
Console.ReadKey();
}
static long Fib(long first, long second, long n)
{
long third = 0;
#不解釋
if (n < 3)
return 1;
/*邏輯是啥宝当？第三個(gè)數(shù)字等于第二個(gè)數(shù)字加上第一個(gè)數(shù)字
*所以要算出第三個(gè)數(shù)字视事，并把現(xiàn)在的第三個(gè)數(shù)字存為第二個(gè)數(shù)字，原第二個(gè)數(shù)字存為第一個(gè)數(shù)字
*這樣下一個(gè)循環(huán)就可以遍歷前一句話了
*/
while (n > 3)
{
long temp = second;
second = first + second;
first = temp;
n--;
}
third = first + second;
return third;
}
}
}
可怕庆揩，只是簡(jiǎn)單的換為循環(huán)就不止要我們?nèi)ダ斫庠鹊墓搅死€要去想邏輯，從而保證邏輯鏈不會(huì)斷掉订晌。這里我們保證邏輯鏈不斷的方法是將f(n－1)和f(n－2)的狀態(tài)賦值給f(n)和f(n－1)以維繼循環(huán)虏辫。
第一章就此結(jié)束
