CSP-J理論(1)

CSP-J理論合集跳轉

目錄

本目錄中所有標題單擊均可以快速跳轉哦

一.排列組合與概率

$\ \ \ \ \ $1.排列

$\ \ \ \ \ $2.組合

$\ \ \ \ \ $3.概率

$\ \ \ \ \ $4.圓排列

$\ \ \ \ \ $5.多重集合的排列

$\ \ \ \ \ $6.錯位排列

二.二進制

$\ \ \ \ \ $1.數據范圍

$\ \ \ \ \ $2.原、補、反碼

$\ \ \ \ \ $3.位運算

三.遞歸問題復雜度分析

$\ \ \ \ \ $1.T(n)=2T(n/2)+n

$\ \ \ \ \ $2.T(n)=2T(n/2)+n^2

$\ \ \ \ \ $3:T(n)=2T(n/2)+sqrt(n)

一、排列組合與概率

一:排列

排列:n個數的排法,從第1位到第n位,每一個位置有n-i-1種選擇,最后把每個位置的選擇數相乘,得到: \(n \times n-1 \times n-2 \times ...\times 2 \times 1\),(即n階乘)。如果要在 n 個數里挑 m 個組 m 位數,數量就是$ n \times n-1 \times n-2 \times n-3 \times ... \times n-m+1$,即A(n,m)

二:組合

組合:n個數的選法。

組合和排列的區別在于排列看來,（1,2）和（2,1）是兩種排列,但在組合看來,（1,2）和（2,1）是一種組合。

所以,組合就是在排列的基礎上再/m,比如在n個數里選m個,就是\(n \times n-1 \times n-2 \times n-3 \times ...\times n-m+1\)再\(/m\),即C（n,m）,但是如果我們在n-m+1后面補上一個從n-m乘到1的表達式,那么就變成了n!,但是也要再除以（n-m）!,因為上面乘了（n-m）!,下面也乘（n-m）!,結果不變。

組合數常見結論:C（n,0）=1,C（n,1）=n,C（n,n）=1,C（n,m）=C（n,n-m）。

三:概率

概率:就是選擇物品數量/總數,如probability這個字符串里取字符,取到字符b的概率就是2/字符串的長度11。

四:圓排列

圓排列就是將幾個數圍成一圈的排列。

如下面這個排列

就是一個圓排列。

圓排列的特點是將圓旋轉，仍然是同一個圓排列，如

和

都是同一個圓排列

圓排列的排列數是(n-1)!

五:多重集合的排列

多重集合是指如{1,1,2,3,3}這樣的集合。假設這個集合里有n種數，每個數都有無限個，要選出k個，排列數就是\(n^k\)。

但如果每種數的數量固定，設第一種數的數目為\(a_1\)、第二種為\(a_2\)...那么排列數就是\(\frac{n!}{a_1!a_2!...a_k!}\)

六:錯位排列

錯位排列是指第i個位置不是i的排列，如{3,2,1}

錯位排列的排列數是

二、二進制

一:數據范圍

int類型的數據范圍是\(-2^{31}\to2^{31}-1\)

unsigned int類型的數據范圍是\(0\to2^{32}-1\)

long long類型的數據范圍是\(-2^{63}\to2^{63}-1\)

unsigned long long類型的數據范圍是\(0\to2^{64}-1\)

二:原、補、反碼

原碼的第一位是符號位，用于表示正負，正為0，負為1，其他位就是這個數的二進制

反碼是原碼除符號位取反（0變1,1變0）

補碼是反碼+1

三:位運算

x<<y就是將x乘上\(2^y\)，x>>y就是將x除以\(2^y\)（向下取整）。

&：每一位都為1就是1

|：每一位有1就是1

^：每一位不同就為1，相同為0

~：對每一位進行取反（包括符號位）

lowbit：用于求得一個數二進制下最低位的1代表2的幾次方。代碼是x&-x

三、遞歸問題復雜度分析

一:T(n)=2T(n/2)+n

畫出遞歸樹

可以發現每一層都是O(n)，總復雜度為O(nlogn)。

二:T(n)=2T(n/2)+n^2

畫出遞歸樹

把每一層的加在一起，得到 \(n^2+\frac{n^2}{2}+\frac{n^2}{4}+...\)。

我們把 \(n^2\) 提取出來，得到 \(n^2 \times (1+\frac{1}{2}+\frac{1}{4}+...)\)。

我們可以發現右邊的和無論如何都是小于 \(2\) 的，所以總復雜度為O(n^2)。

三:T(n)=2T(n/2)+sqrt(n)

畫出遞歸樹

求和可以得到是 \(\sqrt{n}+2\times\sqrt{\frac{n}{2}}+4\times\sqrt{\frac{n}{4}}+...\)。

我們把 \(\sqrt{n}\) 提取出來，可以得到 \(\sqrt{n}\times(1+\sqrt{2}+\sqrt{4}+...)\)。

利用等比數列求和公式，可以得到括號里是 \(\sqrt{n}\)，與前面的 \(\sqrt{n}\) 相乘，所以得到總復雜度為O(n)。