# W3 - Algorithms
##### `Cs50`
[TOC]
## 進度： [Running Time](https://www.youtube.com/watch?v=4oqjcKenCH8&list=PLhQjrBD2T380F_inVRXMIHCqLaNUd7bN4&index=6&ab_channel=CS50)
let temp = [2,4,1,3,5,6]
let temp = [1,2,3,4,5,6]
# W3 簽到處
# Notes
:::spoiler 黑貓
# Algorithm
- CPU只能一次執行一道指令，要如何有效率的執行程式，得透過優化執行步驟來達成。
## Linear Search
- 逐次拜訪每一個陣列的元素，直到找到我們想要的目標 / 整個陣列拜訪完即停止。
- 時間複雜度O(N)，執行時間會呈線性成長。
```c
bool find_elements_in_array(int * array, int length, int element)
{
for (int i = 0; i < length; i++)
{
if (array[i] == element)
return true;
}
return false;
}
```
## Binary Search
- 直接拜訪陣列中間的元素，如果目標值小於該元素，則改拜訪左邊中間的元素；反之改拜訪右邊並重複執行，直到：
- 找到目標 / 找不到該值 / 目標超過陣列最大/最小值。
- 需先將陣列元素排列大小。
- 時間複雜度O(log(n))，執行時間呈對數成長。
```c
bool find_elements_in_array(int * array, int length, int element)
{
int low = 0, high = length - 1;
int middle = (high + low) / 2;
while (low <= high)
{
if (element == array[middle])
return true;
else if (element < array[middle])
high = middle - 1; // to search left side
else if (element > array[middle])
low = middle + 1; // to search right side
middle = (high + low) / 2;
}
return false;
}
```
## Running Time
- 平均時間複雜度排序 (由慢到快)
$$
O(N^2) > O(NlogN) > O(N) > O(logN) > O(1)
$$
- **最好時間複雜度**
- 在最快的情況，完成的時間
- **最壞時間複雜度**
- 在最慢的情況，完成的時間
:::
:::spoiler Tomas
zero Index - 從0開始的索引
linear search (線性查詢)
- 照順序查詢
binary search (二分查詢)
- 將array排序後，從中間查詢。
```
- target > array[middle] ? array[middle + 1]:array[middle - 1]....
```
- 排序的cost
**big O : 最壞情況下的時間複雜度(upper bound) - 最泛用**
- 表示最壞情況下以f(n)量級增長
$$
O(N^2) > O(NlogN) > O(N) > O(logN) > O(1)
$$
**Omega : 最好狀況下的時間複雜度(lower bound)**
- 表示最好情況下以f(n)量級增長
**Theta : 表示平均的狀況下 (tight bound)**
:::
# W4 structs
## 進度： [structs](https://youtu.be/4oqjcKenCH8?list=PLhQjrBD2T380F_inVRXMIHCqLaNUd7bN4&t=3500)
# W4 簽到處
# Notes
:::spoiler KellyLee
==search.c==
• [strcmp](https://manual.cs50.io/3/strcmp) - compare two strings
*Header Files*
\#include <cs50.h>
\#include <string.h>
*Prototype*
int strcmp(string s1, string s2);
• echo $?
是一個用於顯示上一個執行命令的退出狀態碼的命令。當您運行一個命令時，該命令將執行並返回一個退出狀態碼，它通常表示命令的執行結果。
如果退出狀態碼為0，通常表示命令成功執行。
如果退出狀態碼不為0，通常表示命令執行時遇到了錯誤或問題。
---
==structs==
```
typedef struct
{
string name;
string number;
}
person;
```
這段代碼定義了一個結構（struct），名稱為 person。
:::
:::spoiler tomas
## linear search
import library
```c
#include <cs50.h>
#include <stdio.h>
#include <string.h>
```
main code
```c
int main(void)
{
// int number[] = {20,50,10,5,100,1,50}
string strings[] = {"battleship", "boot", "cannon", "iron", "thimble"};
// int n = get_int("Number: ")
string s = get_string("String: ");
// for(int i = 0; i < 7; i++)
for(int i = 0; i < 6; i++)
{
// if(number[i] == n)
if(strcmp(strings[i], s) == 0); // 1 or -1 or 0 base on result //strcmp = string compare
{
printf("Found\n");
return 0;
}
}
printf("Not Found\n");
return 1;
}
```
## phoneBook
import library
```
#include <cs50.h>
#include <stdio.h>
#include <string.h>
```
main
```c
int main(void)
{
string names[] = {"Carter","David"};
string numbers[] = {"0954551235","0987654321"};
string name = get_string("Name: ");
for (int i = 0; i < 2; i++)
{
if(strcmp(names[i],name)==0))
{
printf("Found %s\n",numbers[i]);
return 0;
}
}
printf("Not Found\n");
return 1;
}
```
### custom type (struct)
- C不能設定default value
```
typedef struct
{
string name;
string number;
}
person; //typename
```
fixed
```c
typedef struct
{
string name;
string number;
// string address;
}
person;
int main(void)
{
person people[2];
people[0].name = "Carter";
people[0].number = "0987654321"
people[1].name = "David"
people[1].number = "0912345678"
string name = get_string("Name: ");
for (int i = 0; i < 2; i++)
{
if(strcmp(people[i].name, name) == 0))
{
printf("Found %s\n",people[i].number);
return 0;
}
}
printf("Not Found\n");
return 1;
}
```
:::
## 進度： [Comparing Algorithms](https://youtu.be/4oqjcKenCH8?t=5209)
# Notes
:::spoiler Tomas
## Sort
需要進行權衡(trade off)是否需要進行 sort。
- Select sort
- 使用一個變數儲存特定條件的 value，並且檢查完一輪後，將與儲存 value 相同的元素和第一個尚未整理的元素交換位置。
- 反覆選擇最小的元素。
-
- bubble sort
- 專注於局部問題。
- 在比較的當下就進行處裡。
-
## 計算複雜度
let tempArr = [1,2,3,4,6...] //length: 10
$$
O(N^2) > O(NlogN) > O(N) > O(logN) > O(1)
$$
- Select sort
- n - 1
- n² => O(n²)
- same in omega & delta
- bubble sort
- 因為每次選取 2 個元素。
- n - 2
- n² => O(n²)
- omega : (n)
:::
:::spoiler KellyLee
==selection sort==
```
For i from 0 to n–1
Find smallest number between numbers[i] and numbers[n-1]
Swap smallest number with numbers[i]
```
( 排的最末端是[n-1],因為是從0開始算)
(n-1)+(n-2)+(n-3)+…+1
n(n-1)/2
n^2/2 - n/2
O(n^2)
==Bubble sort==
```
Repeat n-1 times
For i from 0 to n–2
If numbers[i] and numbers[i+1] out of order
Swap them
```
**`For i from 0 to n–2`**: 在每一輪遍歷中，我們從列表的第一個元素開始（索引 0），並遍歷到倒數第二個元素（索引 n-2）。這是因為在每一輪中，我們需要比較相鄰的兩個數字，並且最後一個數字將會是排序過的。
```
5 2 7 4 1 6 3 0
^ ^
2 5 7 4 1 6 3 0
^ ^
2 5 7 4 1 6 3 0
^ ^
2 5 4 7 1 6 3 0
^ ^
2 5 4 1 7 6 3 0
^ ^
2 5 4 1 6 7 3 0
^ ^
2 5 4 1 6 3 7 0
^ ^
2 5 4 1 6 3 0 7
```
代表今天若n=8, For i from 0 to n–2 表示 For 8 from 0 to 8–2
因為最後一個數字和第七個數字排過了,所以不用列入
(n-1)*(n-1)
n^2-2n+1
O(n^2)
:::
# W5 簽到處
## 進度： [Finish Algorithms](https://youtu.be/4oqjcKenCH8?t=5209) + lab1
# Notes
:::spoiler Tomas
## 總結：
### 時間複雜度：
- Omega（Ω）：Ω(n)。
最佳情況時間複雜度
- Theta（Θ）：Θ(n^2)。
平均情況時間複雜度。
- 大O（O）：O(n^2)。
最壞情況時間複雜度
### 3種排序法：
#### 冒泡排序（Bubble Sort）：
冒泡排序是一種簡單的排序算法，它的基本思想是不斷地比較相鄰的兩個元素，如果它們的順序不正確，就交換它們，直到整個數列有序為止。
#### 時間複雜度
- Omega（Ω）：Ω(n)。 當數列已經完全有序時，冒泡排序的最佳情況時間複雜度是線性的，因為不需要任何交換操作。
- Theta（Θ）：Θ(n^2)。 冒泡排序的平均情況和最壞情況時間複雜度都是二次的，因此整體時間複雜度是Θ(n^2)。
- 大O（O）：O(n^2)。 冒泡排序的最壞情況時間複雜度是二次的，因此最壞情況下需要n^2次比較和交換。
#### 步驟：
從第一個元素開始，比較它和下一個元素。
如果它比下一個元素大，則交換它們的位置。
移動到下一對相鄰元素，重複步驟1和2，直到遍歷整個數列。
重複以上步驟，直到沒有交換發生，表示數列已經排序完成。
冒泡排序的時間複雜度是O(n^2)，其中n是元素的數量。它雖然簡單，但對於大型數列來說效率較低。
#### 選擇排序（Selection Sort）：
選擇排序是另一種簡單的排序算法，它的主要思想是在每一輪選擇最小的元素，然後將其放在適當的位置。
#### 時間複雜度
- Omega（Ω）：Ω(n^2)。 選擇排序的最佳情況和平均情況時間複雜度都是二次的，因為它總是需要比較並交換元素。
- Theta（Θ）：Θ(n^2)。 選擇排序的平均情況和最壞情況時間複雜度都是二次的，因此整體時間複雜度是Θ(n^2)。
- 大O（O）：O(n^2)。 選擇排序的最壞情況時間複雜度是二次的，因此最壞情況下需要n^2次比較和交換。
#### 步驟：
找到數列中的最小元素。
將最小元素與第一個元素交換位置。
在剩餘的元素中找到最小元素，將其與第二個元素交換位置。
重複以上步驟，直到整個數列有序。
選擇排序的時間複雜度也是O(n^2)，它在實踐中對於小型數列可能表現得更好一些。
#### 合併排序（Merge Sort）：
合併排序是一種分治算法，它將數列分為較小的子數列，然後合併這些子數列以獲得排序後的結果。
#### 時間複雜度
- Omega（Ω）：Ω(n log n)。 合併排序的最佳情況、平均情況和最壞情況時間複雜度都是線性對數的，因此最佳、平均和最壞情況下都具有相同的Ω(n log n)時間複雜度。
- Theta（Θ）：Θ(n log n)。 合併排序的整體時間複雜度是線性對數的，因此在不同情況下都是相同的。
- 大O（O）：O(n log n)。 合併排序的最壞情況時間複雜度是線性對數的，因此最壞情況下需要n log n次比較和合併操作。
#### 步驟：
分割：將原始數列分為兩個較小的子數列，直到每個子數列只包含一個元素。
合併：將兩個子數列合併為一個新的有序數列，重複此過程，直到合併完成並得到最終的排序結果。
合併排序的時間複雜度是O(n log n)，其中n是元素的數量。它是一個穩定且高效的排序算法，通常用於處理大型數列。
:::spoiler Lab 根據提供的數據 & 三種 Sort 方式判斷分別為何。
### Sort1 (bubble)
- reversed50000
```
real 0m5.243s
user 0m4.501s
sys 0m0.319s
```
- random50000
```
real 0m5.924s
user 0m5.211s
sys 0m0.322s
```
- sorted50000
```
real 0m0.414s
user 0m0.022s
sys 0m0.274s
```
### Sort2 (merge)
- reversed50000
```
real 0m0.393s
user 0m0.022s
sys 0m0.275s
```
- random50000
```
real 0m0.567s
user 0m0.039s
sys 0m0.272s
```
- sorted50000
```
real 0m0.470s
user 0m0.033s
sys 0m0.283s
```
### Sort3 (select)
- reversed50000
```
real 0m2.573s
user 0m1.978s
sys 0m0.320s
```
- random50000
```
real 0m2.432s
user 0m1.850s
sys 0m0.307s
```
- sorted50000
```
real 0m2.325s
user 0m1.847s
sys 0m0.293s
```
現在我們可以根據得出的數據以及對應演算法的時間複雜度來判斷分別使用了甚麼演算法。
bubble sort:
Omega : n
theta : n^2
BigO : n^2
select sort:
Omega : n^2
theta : n^2
BigO : n^2
merge sort:
Omega : Θ(n log n)
theta : Θ(n log n)
BigO : Θ(n log n)
reversed 對應 BigO
random 對應 theta
sorted 對應 omega
Sort 1 在三組數據中，兩組相近，一組極快。
所以會是 bubble。
Sort 2、3 在三組數據中，三組數據都接近，但是還是有效率的差距，可以知道 n log n 速度> n^2。
所以 2 是 merge ，3 是 select
:::spoiler problem set1
## 需求
執行 plurality 帶入候選人以及票數，會顯示分別投誰。
return 最高票
同票則回選2人
```c
#include <cs50.h>
#include <stdio.h>
#include <string.h>
// Max number of candidates
#define MAX 9
// Candidates have name and vote count
typedef struct
{
string name;
int votes;
}
candidate; // 宣告型別
// Array of candidates
candidate candidates[MAX]; //宣告這個 array 最大長度為9
// Number of candidates
int candidate_count;
// Function prototypes
bool vote(string name); // vote 輸入一個name, return 為 boolean
void print_winner(void); //print_winner 沒有 input & return
int main(int argc, string argv[]) //argc 為接收參數(候選人名稱) //argv 用於儲存參數(候選人名稱
{
// Check for invalid usage
if (argc < 2) //輸入的參數數量(包含plurality) 未滿3個 (沒有2個候選人)
{
printf("Usage: plurality [candidate ...]\n");
return 1;
}
// Populate array of candidates
candidate_count = argc - 1;
if (candidate_count > MAX) //超過 array 最大上限
{
printf("Maximum number of candidates is %i\n", MAX);
return 2;
}
for (int i = 0; i < candidate_count; i++)
{
candidates[i].name = argv[i + 1]; //candidates[i]中的name 會是 argv[i+1] //因為 argv 中的[0] 是 plurality自己
candidates[i].votes = 0; //所有人的票數為0
}
int voter_count = get_int("Number of voters: "); //幾個投票者
// Loop over all voters
for (int i = 0; i < voter_count; i++)
{
string name = get_string("Vote: "); //投給誰
// Check for invalid vote
if (!vote(name))
{
printf("Invalid vote.\n");
}
}
// Display winner of election
print_winner();
}
// Update vote totals given a new vote
bool vote(string name) //透過判斷輸入的 name 確定是否與候選人名單符合
{
for(int i = 0; i < candidate_count; i++)
{
if( strcmp(name, candidates[i].name) == 0)
//strcmp(string compire) 是否為string
// strcmp(parmas1,parmas2) return 1/0/-1根據字典順序排序
// 根據 Unicode 從第一個字符開始比對
{
candidates[i].votes++;
return true;
}
}
return false;
}
// Print the winner (or winners) of the election
void print_winner(void) //找出最高票數者
{
//儲存最高的票數
//找出票數 == 最高票數的人
int maxvotes = 0;
string winner;
for(int i = 0; i < candidate_count; i++)
{
if(candidates[i].votes > maxvotes)
{
maxvotes = candidates[i].votes;
}
}
for(int i = 0; i < candidate_count; i++)
{
if(candidates[i].votes == maxvotes)
{
winner = candidates[i].name;
printf("%s\n",winner);
}
}
return;
}
```
:::
:::spoiler Kellylee
problem set1
https://www.youtube.com/watch?v=XBHoD6IbSms
```c
#include <cs50.h>
#include <stdio.h>
#include <string.h>
// Max voters and candidates
#define MAX_VOTERS 100
#define MAX_CANDIDATES 9
// preferences[i][j] is jth preference for voter i
int preferences[MAX_VOTERS][MAX_CANDIDATES];
// Candidates have name, vote count, eliminated status
typedef struct
{
string name;
int votes;
bool eliminated;
}
candidate;
// Array of candidates
candidate candidates[MAX_CANDIDATES];
// Numbers of voters and candidates
int voter_count;
int candidate_count;
// Function prototypes
bool vote(int voter, int rank, string name);
void tabulate(void);
bool print_winner(void);
int find_min(void);
bool is_tie(int min);
void eliminate(int min);
int main(int argc, string argv[])
{
// Check for invalid usage
if (argc < 2)
{
printf("Usage: runoff [candidate ...]\n");
return 1;
}
// Populate array of candidates
candidate_count = argc - 1;
if (candidate_count > MAX_CANDIDATES)
{
printf("Maximum number of candidates is %i\n", MAX_CANDIDATES);
return 2;
}
for (int i = 0; i < candidate_count; i++)
{
candidates[i].name = argv[i + 1];
candidates[i].votes = 0;
candidates[i].eliminated = false;
}
voter_count = get_int("Number of voters: ");
if (voter_count > MAX_VOTERS)
{
printf("Maximum number of voters is %i\n", MAX_VOTERS);
return 3;
}
// Keep querying for votes
for (int i = 0; i < voter_count; i++)
{
// Query for each rank
for (int j = 0; j < candidate_count; j++)
{
string name = get_string("Rank %i: ", j + 1);
// Record vote, unless it's invalid
if (!vote(i, j, name))
{
printf("Invalid vote.\n");
return 4;
}
}
printf("\n");
}
// Keep holding runoffs until winner exists
while (true)
{
// Calculate votes given remaining candidates
tabulate();
// Check if election has been won
bool won = print_winner();
if (won)
{
break;
}
// Eliminate last-place candidates
int min = find_min();
bool tie = is_tie(min);
// If tie, everyone wins
if (tie)
{
for (int i = 0; i < candidate_count; i++)
{
if (!candidates[i].eliminated)
{
printf("%s\n", candidates[i].name);
}
}
break;
}
// Eliminate anyone with minimum number of votes
eliminate(min);
// Reset vote counts back to zero
for (int i = 0; i < candidate_count; i++)
{
candidates[i].votes = 0;
}
}
return 0;
}
// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
// name is a match for the name of a valid candidate
for(int i = 0; i < candidate_count; i++)
{
if(strcmp(candidates[i].name, name) == 0)
{
//then you should update the global preference array to indicate
//that the voter has that candidate as their rank preference
//i值是候選人的編號
preferences[voter][rank] = i;
return true;
}
}
return false;
}
// 目標是對未淘汰的候選人進行制表
void tabulate(void)
{
for(int i = 0; i < voter_count; i++)
//查看每位voter及其candidate
{
for(int j = 0; j < candidate_count; j++)
{
if(!candidates[preferences[i][j]].eliminated)
//加上!尋找未被淘汰的候選人
{
candidates[preferences[i][j]].votes += 1;
break;
}
}
}
return;
}
// Print the winner of the election, if there is one
bool print_winner(void)
{
int majority = (voter_count /2) + 1;
for (int i = 0; i < candidate_count; i++)
{
if(candidates[i].votes >= majority)
{
printf("%s",candidates[i].name);
return true;
}
}
return false;
}
// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
int min = INT_MAX;
for(int i = 0; i < candidate_count; i++)
{
if(!candidates[i].eliminated && candidates[i].votes < min)
{
min = candidates[i].votes;
}
}
return min;
}
// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{
int remaining_candidates = 0;
int candidates_with_min_votes = 0;
for(int i = 0; i < candidate_count; i++)
{
if(!candidates[i].eliminated)
{
remaining_candidates += 1;
if(candidates[i].votes == min)
{
candidates_with_min_votes +=1;
}
}
}
if(remaining_candidates == candidates_with_min_votes)
{
return true;
}
return false;
}
// Eliminate the candidate (or candidates) in last place
void eliminate(int min)
{
for(int i = 0; i < candidate_count; i++)
{
if(!candidates[i].eliminated && candidates[i].votes == min)
{
candidates[i].eliminated = true;
}
}
return;
}
```
Sign in with Wallet
Connect another wallet