第139封信 | 股票最長的增長期
9:52 9.04 MB
信件朗讀者：寶木
思無邪零聚，你好！
今天再和你一同分析一道Google的面試題，這是我在Google面試時被考到的第一道題。為了便于你理解這道題惭嚣，我把原題用另一種方式表述一下。
假如你研究股票投資悔政，可能好奇一只股票最長的有效增長期是哪一個時間段晚吞，即從哪天開始到哪天結(jié)束。這樣從理論上講谋国，如果有一個預(yù)言家告訴你這個信息槽地，可以得到理論上最大的收益。
那么什么是有效的增長期呢芦瘾？所謂有效的增長捌蚊，是比大盤漲得快的那部分。我在之前很多介紹投資的信中講過近弟，任何一家公司最終都會消亡缅糟，因此它的股票在一定階段后的表現(xiàn)會一天不如一天，直到這家公司不再存在祷愉。從那一天開始窗宦，投資它們就沒有意義了赦颇。當(dāng)然，由于通貨膨脹赴涵，此后股票價格可能還會上漲沐扳，但并不意味著它們的價值在增加。
事實上句占，只有當(dāng)一只股票的價格漲速超過股指的時候，購買和持有它才有意義躯嫉。因此纱烘，我們要扣除掉整個市場對股票價格的影響，當(dāng)一只股票每天上漲的速度超過股票指數(shù)祈餐，我們就認為它的有效增長是正數(shù)擂啥，否則就是負數(shù)。為了你便于理解帆阳，我們可以看一個具體的例子哺壶。
股票ABC每日的有效增長如下：
其中每一個數(shù)字代表它今天比昨天的增長減去股票指數(shù)增長后的凈值，單位是基本點蜒谤，也就是萬分之一山宾。第一天它比大盤多漲了1.5個基本點，第二天又比大盤跌了12.3個基本點鳍徽，以此類推资锰。從第一天到第十三天，ABC的股票比大盤累計有效增長為27.7個基本點阶祭。注意绷杜，股票的增長其實應(yīng)該做乘法計算復(fù)合增長，但是這里為了簡單易懂濒募，我就采用加法計算簡單增長了鞭盟，在算法上它們并沒有區(qū)別。
假如有個預(yù)言家能告訴你哪天開始買入股票瑰剃，哪天賣出齿诉，你就能最大地獲益。從上面的數(shù)據(jù)可以看出培他，你應(yīng)該在第5天買入鹃两，在第10天賣出，這樣你的累計有效增長就比股指高出52.4個基本點舀凛。在此之前和之后俊扳，持有ABC公司的股票都不如持有指數(shù)基金。
在實際的股票交易中猛遍，思科公司和英特爾公司的股票馋记，最佳的持有區(qū)間是從它們上市一直持有到2000年的某一天号坡，再往后，持有它們的股票就不如持有標(biāo)普500指數(shù)或者道瓊斯指數(shù)了梯醒。這個最長點增長期宽堆，是一個投資人所能最大獲益的上限，通常沒有人能夠捕捉得那么準(zhǔn)確茸习，但是上述的區(qū)間畜隶，對于股票研究還是有意義的，它可以作為分母來衡量投資人的表現(xiàn)号胚。
接下來Google的問題是籽慢，如何確定起始的日期和終止的日期？
對于這道問題猫胁，有四種可行的方法箱亿，它們計算的復(fù)雜度從高到低依次下降。
方法一弃秆，做一次三重循環(huán)届惋，其實就是中學(xué)里學(xué)的排列組合的方法。我們先假設(shè)一共有K天菠赚。
如果起始和終止日期能夠確定脑豹，從起始日到終止日，做一次連加衡查，就算出某個特定的起始日到終止日之間股票的有效漲幅晨缴，這是一重循環(huán)。當(dāng)然起始日可以是第一天到第K天中的任意一天峡捡，這是第二重循環(huán)击碗。終止日也可以有這么多選擇（當(dāng)然終止日要不早于起始日），這是第三重循環(huán)们拙。于是起始和終止日本身就有KxK／2種選擇稍途。每一種選擇最多要做K次加法（最少做零次），平均做K／2次砚婆。因此這種方法的復(fù)雜度是O（K^3）械拍，即K的三次方。如果已經(jīng)忘記了復(fù)雜度O的概念装盯，可以翻一翻之前的內(nèi)容坷虑。
這個方法無疑能夠完成任務(wù)，但是做了太多的無用功埂奈。如果遇上GE這樣的百年老店迄损，數(shù)據(jù)有幾萬個點，幾萬的三次方可是幾十萬億账磺，計算量非常大芹敌。當(dāng)然痊远，這個方法稍加改進就能快很多，于是就有了下一種方法氏捞。
方法二碧聪，做兩重循環(huán)。
在上述方法中液茎，我們可以看到這樣一個現(xiàn)象：對于某個特定的起始日期逞姿，比如從第500天開始，我們想知道終止日期設(shè)在第1000天好呢捆等，還是第1001天更好哼凯。這件事很簡單，只要看看第1001天的有效漲幅是正的楚里，還是負的就可以了。如果是正的猎贴，那么顯然要持有到1001天班缎，因為多漲了一天，這時她渴，我們要把累計到第1001天的漲幅記錄下來达址，但是到第1000天的累計漲幅其實后面不會再用到了，就可以刪掉了趁耗。
相反沉唠，如果1001天的漲幅是負的，那并不能說明股票從此就該拋掉苛败，因為第1002天满葛、第1003天……都還有機會大漲。在這種情況下罢屈，要保留截止到第1000天的累計增幅嘀韧，然后再往后一直看，直到有一天缠捌，累計增幅超過它锄贷，才可以把累計到第1000天的數(shù)據(jù)刪掉，用新的累計增幅替代它曼月。這樣一來谊却，設(shè)定一個初始日期，掃描一遍哑芹，就能找到從這個起始日期開始炎辨，到哪一天結(jié)束，累計的增幅最大聪姿。這個過程需要K次加法和K次比較蹦魔。
由于起始日期還不確定激率，它可以是從第一天到最后一天（第K天）中間的任何一天，因此要試K次勿决，于是這種算法的復(fù)雜度是O（K^2）乒躺。如果K有好幾萬，計算量是十幾億低缩，比前一種方法已經(jīng)減少了上萬倍嘉冒。但是，這個問題還有更有效的解法咆繁。
方法三讳推，這個方法比較難理解，你只要記住這是分治算法的應(yīng)用就好了玩般。它和方法二的關(guān)系银觅，就如同過去介紹的歸并排序和冒泡排序的關(guān)系。
更具體一點講坏为，就是把股票漲跌的時間從中間一分為二究驴，變成兩個階段，而兩個小問題加起來也要比一個大問題簡單些匀伏。然后你再把兩個小問題分成四個更小的問題洒忧，直到分不下去為止。最后這個方法的復(fù)雜度可以降到O（N x Log N）够颠，對于GE這樣有幾萬天交易記錄的公司熙侍，計算量為百萬左右，這比十幾億又小了上千倍履磨。然而蛉抓，它依然不是最好的方法。
方法四剃诅，正反兩遍掃描的方法芝雪。
這個方法也是對方法二的改進。在方法二中综苔，我們其實能夠找到股票從此走下坡路的時間惩系，比如我們能知道在第1005天之后，股票的累計漲幅達到了頂點如筛，再往后雖然有漲有跌堡牡，但累計下來沒有增長，因此就不用考慮了杨刨，這一天就定為截止日期晤柄，或者說拋售的日期。但是妖胀，我無法知道股票在什么時候開始進入上升期的芥颈。因此在方法二中我們假設(shè)了所有的情況都是合理的惠勒。
然而，如果我們能夠逆向思考這個問題爬坑，從最后一天往前回溯纠屋，用同樣的辦法，就能找到股票上升期的開始日期盾计。這兩個日期之間就是該購買和持有ABC公司股票的時間段售担。
因此，第四種算法只要掃描兩遍數(shù)據(jù)署辉，就能解決所有的問題族铆，其復(fù)雜度是O（N），也就是說是線性的哭尝。對于GE這樣有幾萬天交易的股票哥攘，計算量只有幾萬而已，比上一種方法又快了幾十倍材鹦。
從方法一到方法四逝淹，我們將一個問題的計算量從幾十萬億，降低到幾萬侠姑。平庸的方法和好的方法差距如此之大，對此不知道你對此有何感想箩做。我在Google面試時莽红，大約花了一刻鐘時間想到了方法四，面試我的本杰明估計很滿意邦邦，因為他對我的態(tài)度馬上就熱情了很多安吁，而我也感嘆他們的面試題出得精妙。
這道面試題唯一的缺陷是無法避免刷題燃辖，因為在找到方法四后鬼店，就很難再往深了繼續(xù)提問。
最后總結(jié)一下今天的內(nèi)容黔龟。
首先妇智，我再次向你展示了計算機科學(xué)中經(jīng)常會遇到的量級的差別。
其次氏身，在金融上巍棱，任何一只股票都有跑不贏大盤的時候，因為任何公司最終會消亡蛋欣。道瓊斯最早的12只成分股公司和隨后的20個公司航徙，今天只剩下GE一家了。而且如果不出意外陷虎，GE的股票從此也很難再跑贏大盤了到踏。因此杠袱，玩單只股票其實是很危險的事情。
當(dāng)然窝稿，最關(guān)鍵的是楣富，逆向思維永遠重要。
關(guān)于股票投資大家可以參考我在《硅谷來信》中第145封信到第149封信的內(nèi)容讹躯。
最后菩彬，如果你是計算機專業(yè)的人，希望今天的方法能夠有助于你分析更多的算法類面試題潮梯。另外骗灶，也向你透露一個信息，頂級的計算機公司更看重算法能力秉馏，而非編程能力耙旦。
