# 1.算法分析基本步骤

1. Observations: 观察程序运行的特点（比如执行时间等）
2. Mathematical Models： 建立一些模型
3. 使用算法理论分析

# 2. observations

3 SUM问题 1. 排序，O(logN)
2. 计算所有两两组合的值(a[i]+a[j])，O(N^2)
3. 在有序序列中二分查找-(a[i]+a[j]),O(logN)
4. 因此总的复杂度2O(logN)*O(N^2)，即O(N^2logN)

PS: 除了3加问题，还有1加问题（N个数中找为0的数），2加问题（N个数找2个加起来为0的数）

# 3. 按照增长速度对算法分类 # 4. 算法理论分析 1. 大Theta: 例如theta(N^2)表示运行时间在N^2这个数量级
2. O: 例如O(N^2)表示运行时间在这个N^2数量级，并且可能更加的小，例如常数时间或者线性时间，即表示的是最坏情况（上限）
3. 欧米伽： 例如O(N^2)表示运行时间在这个N^2数量级，并且可能更加的大，即表示的是最好情况（下限）
4. 波浪号：用于近似
{"ft_lang_label":"__label__zh","ft_lang_prob":0.9835774,"math_prob":0.99312514,"size":803,"snap":"2021-31-2021-39","text_gpt3_token_len":668,"char_repetition_ratio":0.09762203,"word_repetition_ratio":0.0,"special_character_ratio":0.25653797,"punctuation_ratio":0.07438017,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.955662,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12],"im_url_duplicate_count":[null,4,null,4,null,4,null,4,null,4,null,4,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-07-23T18:05:32Z\",\"WARC-Record-ID\":\"<urn:uuid:4e764bd3-248a-4d71-a748-6e18f4b91f41>\",\"Content-Length\":\"15774\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:c979539d-7a97-4020-bb26-6a9ac1ff091a>\",\"WARC-Concurrent-To\":\"<urn:uuid:c3e6074c-5a81-4ce9-a874-313aa1d716f7>\",\"WARC-IP-Address\":\"192.95.36.177\",\"WARC-Target-URI\":\"https://kaimingwan.com/post/ji-chu-zhi-shi/suan-fa/-2-analysis-of-algorithms\",\"WARC-Payload-Digest\":\"sha1:WWG4ZZYWELLELEVX26ZFM5GNGDL7SUGS\",\"WARC-Block-Digest\":\"sha1:XH7YIFY6Z6U4HSMH5RLCPNK3YQSRPI4E\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-31/CC-MAIN-2021-31_segments_1627046150000.59_warc_CC-MAIN-20210723175111-20210723205111-00402.warc.gz\"}"}