: The ability to understand various constraints and requirements for programming and find the best solution
- The ability to connect knowledge of programming languages, libraries, data structures, and algorithms to create the bigger picture
- Space efficiency refers to how much memory space is required
- Time efficiency refers to how much time is required
- When efficiency is expressed inversely, it becomes complexity
- The higher the complexity, the lower the efficiency
- Processing time varies depending on hardware environment
- Processing time varies depending on software environment
- Therefore, analysis is difficult due to these environmental differences
- Time (or space) complexity is expressed as a function of input size, and this function is usually a polynomial with multiple terms
- T(n): Execution time
- T(n) = O(f(n)) only when there exist constants c and n0 such that T(n) <= c*f(n)
- However, constants c and initial value n0 are independent of the value of n
- O-notation
- Represents the asymptotic upper bound of complexity
- If complexity is T(n) = 2n^2 - 7n +4, then the O notation of T(n) is O(n^2)
- The simplified expression of T(n) is n^2
- "Even in the worst case, it will be at most this much"
- Big-Omega notation
- Represents the asymptotic lower bound of complexity
- "At least this much will be required"
Omega < Theta < Big O
O(1)- Constant time
O(logn)- Logarithmic time
O(n)- Linear time
O(nlogn)- Log-linear time
O(n^2)- Quadratic time
O(n^3)- Cubic time
O(2^n)- Exponential time
- Integers can be represented in 2 bytes or 4 bytes
- When exceeding the range:
- Either discard
- Or apply correction
- Integers have a sign bit at the front
- Determines whether a positive integer value stored in a variable is odd or even
- N%2
- Uses % operation to determine if the last bit value is 1 or 0, determining odd or even
- Has the value of 2^n
- Represents the number of all subsets when there are n elements
Power set(all subsets)- All subsets including the empty set and itself
- Calculating the 2 cases where each element is included or not included gives the number of all subsets
- The calculation result indicates whether the j-th bit of i is 1 or not
def Bbit_print(i):
output = ''
for j in range(7, -1, -1):
output += "1" if i&(1<<j) else "0"
print(output)
for i in range(-5, 6):
print("%3d = " %i, end='')
Bbit_print(i)- Refers to the method of arranging multiple consecutive objects in a one-dimensional space such as computer memory, and differs by HW architecture
Caution!- When converting between byte units and word units for speed improvement, incorrect understanding can cause errors
- Usually the larger unit comes first
- Network
- ex) internet protocol, IBM z/architecture (only some mainframe computers..)
- Smaller unit comes first
- Most desktop computers
- ex) Intel, ARM processor
# ver1)
n = 0x00111111
if n&0xff: #0xff = 11111111!
print("little endian")
else:
print("big endian")
print('-'*20)
#ver2) Using python sys library
import sys
if sys.byteorder == "little":
print("Little endian platform")
else:
print("Big endian platform")- The difference between mathematical real numbers and computer floating-point numbers
- Computers cannot perfectly represent all real numbers due to limited memory
- Therefore, approximation is used, which can lead to errors
- Uses IEEE 754 standard
- Single precision (32-bit): 1 sign bit + 8 exponent bits + 23 mantissa bits
- Double precision (64-bit): 1 sign bit + 11 exponent bits + 52 mantissa bits
- Due to rounding errors, direct comparison may not work correctly
- Use epsilon (small value) for comparison
def is_equal(a, b, epsilon=1e-9):
return abs(a - b) < epsilon- Using Big-O notation
- Analyzing algorithm complexity without implementation
- Independent of hardware and software environment
- Measuring actual execution time
- Depends on hardware and software environment
- Useful for comparing actual performance
- Analyzing which parts of the program consume the most time
- Helps identify bottlenecks
- Various profiling tools available by language
- Try all possible solutions
- Simple but often inefficient
- Useful when problem size is small
- Divide problem into smaller subproblems
- Solve subproblems recursively
- Combine solutions
- Examples: Merge Sort, Quick Sort
- Make locally optimal choice at each step
- Hope to find global optimum
- Not always optimal, but often efficient
- Examples: Huffman Coding, Dijkstra's Algorithm
- Break down problem into overlapping subproblems
- Store solutions to avoid redundant calculations
- Examples: Fibonacci sequence, Longest Common Subsequence
- Build solution incrementally
- Abandon partial solutions that cannot lead to complete solution
- Examples: N-Queens problem, Sudoku solver
- Fixed-size sequential collection
- Random access: O(1)
- Insertion/Deletion: O(n)
- Dynamic collection of nodes
- Sequential access: O(n)
- Insertion/Deletion: O(1) if position known
- Last In First Out (LIFO)
- Push/Pop operations: O(1)
- Applications: Expression evaluation, Function calls
- First In First Out (FIFO)
- Enqueue/Dequeue operations: O(1)
- Applications: BFS, Process scheduling
- Key-value mapping
- Average case operations: O(1)
- Worst case operations: O(n)
- Hierarchical structure
- Binary Search Tree operations: O(log n) average
- Applications: Searching, Sorting
- Collection of vertices and edges
- Representations: Adjacency matrix, Adjacency list
- Applications: Network routing, Social networks