# [AIdrifter CS 浮生筆錄](https://hackmd.io/bKL1LVo8RaCKn02uHJW2BA) : BCR
# Best conceivable Rutime 最理想執行時間
## BCR: 一個問題能夠得到最好的執行時間
- 程式解題常常會遇到這問題，這演算法還有辦法在優化嗎?　
- 教課書並不會特別提到BCR，但是分析解題非常有用，利用BCR(最佳理想執行時間)，先思考input data和最後輸出的output data考慮其Time Complexity，再去思考最佳情況執行時間的Optimized algorithm，才不會迷失在問題內。

先個經典範例
## 輸出兩陣列中交集元素的index
Given two **sorted** arrays, find the number of elements in common. The arrays are the same length and each has all distinct elements.
Let's start with a good example. We will underline those elements in common.


## Optimzed Algorithms
### Brute Force
:::info
Brute Force : O(n^2)
Optimzed Algo : ?
BCR: O(2N)
:::
- Brute Force:

    vector<int> A = {13, 27, 35, 40, 49, 55, 59};
    vector<int> B = {14, 35, 38, 40, 41, 50, 55};
    vector<pair<int,int>> ans;
    for(size_t i=0;i<A.size();i++)
        for(size_t j=0;j<B.size();j++)
            if(A[i]==B[j])
                ans.push_back({i,j});

- 這邊思考，我們最後輸出paris，最起碼兩個陣列的元素都要access到，所以時間複雜度是O(A+B)=>O(2N)=>O(N)
- 所以最後演算法時間複雜度會介在O(N^2)~O(N) 之間，我們可以開始思考有哪些演算法。
- 補充一下C++ pairs輸出方式

    for(auto p:ans)
        cout<<p.first<<" "<<p.second<<endl;
    
    for(auto [a,b]:ans)
        cout<<a<<" "<<b<<endl;

### Binary Search
:::info
Brute Force : O(n^2)
Optimzed Algo :
- Binary Search : O (N log N)
BCR: O(2N)
:::
- 一定需要去travesal全部的Ａ元素，再去找Ｂ，如果找Ｂ這一段改用binary Search呢？　O(AB) => O(AlogB) => O(NlogN)

int binarySearch(int l,int r, vector<int> &A , int target){
    while(1){
        if(l==r) return -1;
        int mid = l + (r-l)/2;
        if(A[mid] == target) return mid;
        else if(A[mid] > target) r = mid;
        else l = mid + 1;
    }
}

int main(){
    vector<int> A = {13, 27, 35, 40, 49, 55, 59};
    vector<int> B = {14, 35, 38, 40, 41, 50, 55};
    vector<pair<int,int>> ans;
    for(size_t i=0;i<A.size();i++){
        int idx = binarySearch(0, B.size(),B ,A[i]);
        if(idx!=-1)
            ans.push_back({i,idx});
    }    
 }  

### Hash Table
:::info
Brute Force : O(n^2)
Optimzed Algo :
- Binary Search : O (N log N)
- Hash Table : O(N)
BCR: O(2N)
:::
- 有辦法比O(logn)還要快嗎？，事實上用hash table先建表後，之後每次search B都是O(1)，所以現在最快就是O(A)*O(1) => O(N)，因為有BCR，我們知道我們不可能有時間複雜度更快的方法了，我們要**想辦法減少空間複雜度了**。

    vector<int> A = {13, 27, 35, 40, 49, 55, 59};
    vector<int> B = {14, 35, 38, 40, 41, 50, 55};
    vector<pair<int,int>> ans;
    unordered_map<int,int> T;
    
    for(size_t i=0; i<B.size(); i++)
        T[B[i]] = i;
    
    for(size_t i=0;i<A.size();i++){
        if(T.find(A[i])!=T.end())
            ans.push_back({i, T[A[i]]});
    }   

### Two Pointer
:::info
Brute Force : O(n^2)
Optimzed Algo :
- Binary Search : O (N log N)
- Hash Table : O(N)
- Two Pointer: O(N), Space O(N)
BCR: O(2N)
:::

先想想剛剛的Binary Search
1. Do a binary search in B for A[0] (13)- not found
2. Do a binary search in B for A[1] (27)- not found
3. Do a binary search in B for A[2] (35)- found at B[1]
4. Do a binary search in B for A[3] (40) - found at B[3]
5. Do a binary search in B for A[4] (49)- not found

我們用BUD檢查
- B: Bottle necks
- 花費最多地方就是O(A)*O(1)，traversal A所有元素，並找Ａ元素元素有沒有在Ｂ的hash table內。已經是BCR，不能再快了。
- U: Unecessary
- 發現Step 4 不需(Unecessary)用Binary Seach，因為35已經找到了，而45一定比35大，所以35在地B[1] 之前都不需要找。
- 這邊用到題目提示的性質 : Sorted Array
- D: Duplicate
- 沒發現重複的code。

利用Uncessary性質，我們改用Two pointer，節省了原本hash table所需要的空間，時間複雜度為BCR O(N)，空間複雜度為O(1)，我們已經無法再優化了！！

vector<int> A = {13, 27, 35, 40, 49, 55, 59};
vector<int> B = {14, 35, 38, 40, 41, 50, 55};
vector<pair<int,int>> ans;
   
int j = 0;
for(size_t i=0;i<A.size();i++){
    while(A[i]>B[j]) 
        j++;
       
    if(A[i]==B[j]) 
        ans.push_back({i ,j});
}    

## Summary
- 可用執行時間作為必須減少哪部分的提示
- 最快就是O(n)，中間可以用哪方法從O(N^2)降到O(N)? 題目提示的sorted過的array就是關鍵。

- 小於或等於BCR的工作都是「免費」的，因不會影響執行時間：
- 想將搜尋時間由O(log n)降至O(1)，可以做「預先計算」，也就是將B陣列的元素全部建成Hash table，而這需花的時間是O(n)。之後就可以直接查Hash Table找到交集元素。建hash table的O(n)比BCR小，不會有任何額外付出。

- BCR告訴我們執行時間已最佳化要無法再優化了，應該要改善其**空間複雜度了**。
- 如果題目前提是「有序」的陣列，如此有機會去掉雜湊桶，減少額外空間，又能在O(n)中解決問題。

- 如果已達成BCR且具有O(1)額外空間(const)。我們知道已不能再做任何最佳化Big O時間或空間，這就是最佳解。

# Ref
解題時的測試與BCR:
https://lucrelin.blogspot.com/2019/05/bcr.html

WORKING TOWARDS BEST CONCEIVABLE RUNTIME (BCR):
https://4tee-learn.blogspot.com/2019/04/working-towards-best-conceivable.html

book: cracking the coding interview