最近被專(zhuān)八考試打斷了翩肌，我來(lái)繼續(xù)更新了箱蟆，哼哧
從今天開(kāi)始研究①PKU陳斌老師的數(shù)據(jù)結(jié)構(gòu)與算法課程帮非，以及②何晗大哥的NLP入門(mén)。
變位詞判斷問(wèn)題
問(wèn)題描述：
這道題展示了同一問(wèn)題的不同數(shù)量級(jí)解法
解法1：逐字檢查
給定列表s1,s2,對(duì)于s1的每個(gè)字符博个，在s2中逐字對(duì)比怀樟，如果在s2中找到了，就“打勾”（這里的“打勾”采用的是把s2中的對(duì)于字符修改成none的方法）盆佣。（同時(shí)要注意往堡，字符串是不可變類(lèi)型械荷，如果要修改，就要先放到列表里面）
如果s1的每一個(gè)字符都能在s2中找到虑灰，則判定為變位詞吨瞎。相反，只要有一個(gè)找不到穆咐，就不是變位詞颤诀。
solution1的代碼：
算法分析：
問(wèn)題規(guī)模：總字符數(shù)n
主要部分在于兩重循環(huán)，外層遍歷s1每個(gè)字符庸娱，將內(nèi)層循環(huán)執(zhí)行n次
內(nèi)存循環(huán)在s2中查找字符着绊，每個(gè)字符的對(duì)比書(shū)谐算，分別是1,2....n中的一個(gè)熟尉，且各不相同
所以總執(zhí)行次數(shù)是1+2+3+.....+n=n(n+1)/2
數(shù)量級(jí)為O（n^2)
解法2：排序比較
思路：將兩個(gè)字符串都按照字母順序排序，最后比較是否相同
代碼：
#重點(diǎn)學(xué)習(xí)一下逐個(gè)比較的技巧
算法分析：
粗看上去只有一個(gè)循環(huán)洲脂，數(shù)量級(jí)是O（n）
但sort不是沒(méi)有代價(jià)的斤儿，其數(shù)量級(jí)差不多是O（n log n）
本算法時(shí)間主導(dǎo)的步驟是排序步驟，所以運(yùn)行時(shí)間數(shù)量級(jí)為O（n log n）
