---
tags: CS50’s Introduction to CS
---
# Week 3
## Introductions of Algorithm
1. Times:
1. Upper bound: O(times)
2. Lower bound: Ω(times)
* CS tends to throw away constant factors.
2. Algorithms:
1. Search Algorithm
1. Binary Search:
1. Introduction: Binary search is used to search a number in a sorted array, Just like
2. Times:
1. Worst-case performance: O(log n)
2. Best-case performance: O(1)
3. Average performance: O(log n)
2. Sort Alorithm
1. Selection Sort:
1. Introduction:
2. Times:
1. Worst-case performance:
* Comparisons: О($n^2$)
* Swaps: О(n)
2. Best-case performance:
* Comparisons: О($n^2$)
* Swaps: O(1)
3. Average performance:
* Comparisons: О($n^2$)
* Swaps: O(n)
2. Bubble Sort:
1. Introduction: Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order.
2. Times:
1. Worst-case performance:
* Comparisons: О($n^2$)
* Swaps: О($n^2$)
2. Best-case performance:
* Comparisons: O(n)
* Swaps: O(1)
3. Average performance:
* Comparisons: О($n^2$)
* Swaps: О($n^2$)
3. Merge Sort::
1. Introduction:
2. Times:
1. Worst-case performance: O(nlogn)
2. Best-case performance: O(nlogn)
3. Average performance: O(nlogn)
## Structure
1. Declaration:

    struct name_of_the_struct
    {
        data_type 1 data_name 1;
        data_type 2 data_name 2;
        ...
        data_type n data_name n;
    }v 1,v 2, ... v n;

1. The members of a structure are stored in memory in the order in which they're declared.
2. Any names declared in structures won't conflict with other names in a program.
2. Initializing:

    struct structure_name
    {
        data_type 1 v_name 1;
        data_type 2 v_name 2;
        ...
        data_type n v_name n;
    }v 1={v 1 a, v 1 b, ... v 1 n},
     v 2={v 2 a, v 2 b, ... v 2 n},
     ...
     v n={v n a, v n b, ... v n n};

1. Expression used in a structure initializer must be constant. (This restriction is relaxed in C99.)
2. An initializer can have fewer members than the structure it's initializing, and any "leftover" members are given 0 as their initial value.
3. Write .v_name=v to assign a specific member.
4. To initialize variables out of the structure definition, we can write

        struct structure_name v={v 1 a, v 1 b, ... v 1 n};

3. Operation on Structures:
1. To access a member within a structure, we write the name of the structure first, then a period, then the name of the member.
2. The members of a structure are L values.
3. The . operator takes precedence over & operator.
4. Arrays can't be copied using the = operator, but an array embedded within a structure is copied when the enclosing structures is copied.
4. Using Typedef to Define a Structure Type

    typedef struct
    {
        ...
    }type_name;

type_name can be used in the same way as the built-in types.
* ※There is another way to define a type:

        struct structure_name
        {
            data_type 1 v_name 1;
            data_type 2 v_name 2;
            ...
            data_type n v_name n;
        }v 1={v 1 a, v 1 b, ... v 1 n},
         v 2={v 2 a, v 2 b, ... v 2 n},
         ...
         v n={v n a, v n b, ... v n n};
        typedef struct structure name v; 

5. Structures as Arguments and Return Values

    //As arguments
    struct structure_name
    {
        ...
    };
    data_type function_name(struct structure_name variable_name,...)

    //As Return Values
    struct function_name(...)
    {
        ...
    }

6. Compound Literals: A compound literal consists of a type name within parentheses, followed by a set of values in braces.

    (struct structure_name){...}

7. Arrays of Structures:

    struct structure_name
    {
       ...
    }
    struct structure_name array_name[size];

1. size is optional.
2. To initialize an array of structure, just use braces to enclose the members.