<style>
.reveal .slides {
text-align: left;
font-size:30px
}
</style>
# Time Complexity and Bitwise
----
# 時間複雜度
- 與**輸入大小**有關的函數
- 可以用來估計程式執行大約的時間
- 用程式執行次數來去估算執行時間
- 通常以大 $O$ 符號表式，ex: $O(N)$、$O(NlgM)、O(k^3)$
----
### 計算大概的執行次數
執行次數無法完全精準的計算
可能受到編譯器優化影響
使得執行次數不是我們所計算的
而只需要計算大概的次數就可以去估算時間
----
### 表達時間複雜度
- 以大$O$符號表示，其中大$O$符號代表"上限"的意思
----
### 計算時間複雜度
1. 估計程式的運算執行次數
2. 將得到的函數最高階項以外的項全部刪掉
3. 把係數拿掉
----
### 迴圈的時間複雜度
迴圈的執行次數\*每次迴圈的時間複雜度
----
```cpp
for(int i=0;i<n;i++)
{
arr[i]=arr[i-1]*a+b; //O(1)
swap(a,b); //O(1)
}
```
$O(n)$
----
```cpp
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(arr[i]>arr[j])
swap(arr[i],arr[j]); //O(1)
}
}
```
執行次數大約是$(n-1)+(n-2)+...+1+0=\frac{1}{2}n(n-1)=\frac{1}{2}n^2+\frac{1}{2}n$
保留最高階項，省略常數
因此時間複雜度是$O(n^2)$
----
```cpp
for(int i=1;i<n;i*=2)
s+=i;
```
$2^i\lt n\Rightarrow i\lt lgn$
因此是$O(lgn)$
在算複雜度時，通常 $lg$、$log$ 代表以 $2$ 為底取 $log$
----
### 遞迴函數的時間複雜度
- 簡單的你們應該會算(?)
- 比較難的等教分治法(Divide&Conquer)時再說
- 很複雜的我也不會
----
### 內建函數的時間複雜度
其實從函數的功能應該可以猜出其複雜度
不然的話就把它記起來(至少常用的函數要知道)
例：memset O(N)、 sort O(NlgN)、 __gcd O(lgN)、lower_bound O(lgN) ...
----
### 實作範例分析
1.
```cpp
for(int i=100000;i<n;i++)
{
for(int j=i-100;j>=1000;j--)
cout<<i<<" "<<j<<'\n';
}
```
----
1.
```cpp
for(int i=10;i<n;i++)
{
for(int j=i-100;j>=1000;j--)
cout<<i<<" "<<j<<'\n';
}
```
$O(n^2)$
----
2.
```cpp
for(int i=0;i<100000000;i++)
cin>>n,cout<<n*n<<'\n';
```
----
2.
```cpp
for(int i=0;i<100000000;i++)
cin>>n,cout<<n*n<<'\n';
```
$O(1)$
----
3.
```cpp
for(int i=1;i<=n;i++){
sort(arr,arr+i);
}
```
----
3.
```cpp
for(int i=1;i<=n;i++){
sort(arr,arr+i);
}
```
$O(n^2lgn)$ $(\sum\limits_{k=1}^{n}klgk\approx n^2lgn)$
----
4.
```cpp
for(int i=1;i<n;i=i*2){
for(int j=i;j<n;j+=i)
arr[j]+=arr[j-i];
}
```
----
4.
```cpp
for(int i=1;i<n;i=i*2){
for(int j=i;j<n;j+=i)
arr[j]+=arr[j-i];
}
```
$O(n)$ $(n+\frac{n}{2}+\frac{n}{3}+...\approx 2n)$
----
5.
```cpp
void f(int n)
{
if(n==0) return 1;
return f(n-1)*n;
}
```
----
5.
```cpp
void f(int n)
{
if(n==0) return 1;
return f(n-1)*n;
}
```
$O(n)$
----
6.
```cpp
void f(int i){
if(i==n) return;
v[i]=0,f(i+1);v[i]=1,f(i+1);v[i]=2,f(i+1);
}
```
----
6.
```cpp
void f(int i){
if(i==n) return;
v[i]=0,f(i+1);v[i]=1,f(i+1);v[i]=2,f(i+1);
}
```
$O(3^n)$
---
## 為什麼要學時間複雜度
- **判斷一個程式(做法)會不會TLE**
- 可以用側資的範圍去反推演算法
----
1. 把時間複雜度的大$O$符號拿掉，並將題目給定的輸入範圍**上限**帶入函數，令得到的數值為 $T$
2. 一般而言假設c++每秒能跑 $10^8$ 的數量級
3. 假設題目的時限是TL秒，那麼
- 若$T\lt TL\times 10^8$則通常不會TLE
- 若$T\gt TL\times 5\times 10^8$則極有可能拿到TLE
----
### 時間複雜度的好處
- 當你想到一個做法後，在開始寫之前就能先用時間複雜度來判斷是否會TLE，以避免浪費時間在寫必然會TLE的程式
- 在比賽中更容易作時間分配、難度分析
---
## 位元運算
----
### 位元運算
位元運算是對二進位的 0 和 1 做一些處理，然後會出現一些性質和用途。
----
二進位理所當然就只有 true(1) 跟 false(0)，以下是位元運算示範操作
```cpp
AND運算： OR運算：
0 & 0 0 0 | 0 0
0 & 1 0 0 | 1 1
1 & 0 0 1 | 0 1
1 & 1 1 1 | 1 1
XOR運算(⊕)： NOT運算：
0 ^ 0 0 !0 1
0 ^ 1 1
1 ^ 0 1 !1 0
1 ^ 1 0
```
----
### XOR運算
因為 XOR 太多常用性質，所以特別拿出來講。
先來幾個基本原則（bitwise xor 的符號一樣用 ⊕）：
1. A ⊕ B = B ⊕ A，(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)，也就是運算順序不影響結果(有交換律和結合律)。
2. A ⊕ A = 0
3. 若 A ⊕ B = C，則 A ⊕ C = B
4. A ⊕ 0 = A
----
### 左移 右移 運算
C++程式裡使用"<<"與">>"來表示，表示為位元左移(右移)一格
左移時最左邊會補上 0
而右移時最右邊位元會被移除
```=
9=1001 9<<1 = 10010 = 18
15=1111 15>>1 = 111 = 7
常見用法
(x>>1) 快速除2 以及 (x<<1) 和 (x<<1)|1 左子節點和右子節點
```
----
### 補數運算
C++程式裡使用 "~" 來表示，補數運算為逐位元取反
顛倒一個變數的每個位元的 0 和 1
```=
~0=1 ~1=0
常見用法(位元優化dp 總有一天會遇到)
15 & ~(1 << 1) = 13 //將第2個bit設為0
8 |(1 << 2) = 12 //將第3個bit設為1
```
----
### 位元性質
if (status)
while (status)
for ( ; status ; )
以上的 status 都是非 0 就是 true，也就是裡面都是布林值
所以可以常常看到這種寫法
```cpp=
if(array[x]){ //若array[x]的值非零即會進入"True"
cout<<"True";
}
else{ //只有再array[x]==0的時候才會進入這邊
cout<<"False";
}
while(x){ //當x不是0的時候就不會跳出迴圈
x--;
cout<<x<<endl;
}
```
----
規律性質
例題: [[CPE例題](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/12208.pdf)]
詢問 x~y 中所有的數字轉換成二進制後有幾個 1
而當你把位元攤開來之後
0 : 0 0 0 0
1 : 0 0 0 1
2 : 0 0 1 0
3 : 0 0 1 1
4 : 0 1 0 0
5 : 0 1 0 1
6 : 0 1 1 0
7 : 0 1 1 1
8 : 1 0 0 0
|| <span class="spoiler-text"> 每個bit拆開來即可發現規律 </span> ||
----
1 最低的'1'位元
```cpp=
x & -x
```
根據二的補數，-x 為 ~x + 1。因此在這先將 -x 拆開為 ~x + 1 來討論。
x 中最低位的位元 1 經過 not 運算後，將在 ~x 中變為最低位的位元 0。
因此對 ~x 加上 1 後，最低位的位元 0 重新變為位元 1，且其後的位元都將被設定為 0。
2 檢查冪次
是否為二的冪次
```cpp=
(x & -x) == x
```
由於若你為二的冪次，則該數字只會有一個位元(也是最高位元)
----
## 實作例題講解
練習 1 --- XOR 練習
```cpp=
x^=y^=x^=y
```
請問 x,y 各為多少?(用 x 跟 y 表示)
----
拆開來看即為
```cpp=
x = x ^ y;
y = y ^ x;
x = x ^ y;
```
答案為 x 為 y ,y 為 x (相等於 swap ( x , y ))
----
練習 2 --- 優先級的練習
```cpp=
cout<<(15>>1+2);
```
----
```cpp=
cout<< ( 15 >> 1 + 2 );
```
ans : 1
大多數的位元運算子的運算優先級都比較低，
因此此題的計算過程為 1 + 2 = 3 , 15(1111) >> 3 = 1.
所以你不確定優先級的時候最好都要加括號
----
練習 3 --- 常用的技巧
```cpp=
if(x & 1) return 1;
else return 0;
```
```cpp=
return (x & 1);
```
----
```cpp=
if(x&1) return 1;//(奇數)
else return 0;//(偶數)
```
判斷 x 的奇偶性 也是常見用法 (比較快)
由於一個數字的位元組成都是 2 的冪次方
因此 $2^n$ 只有在 n==1 的時候會影響到數字的奇偶性，
故只需要判斷最後一個位元
---
## 提醒大家上禮拜常見的錯誤
---
## 練習和提問時間
[作業連結 ](https://vjudge.net/contest/573669)
{"title":"Time Complexity and Bitwise","contributors":"[{\"id\":\"e4a3af8b-860c-46a0-96f1-558667fdcf41\",\"add\":5698,\"del\":231}]","description":"與輸入大小有關的函數"}