Algorithmic complexity
暂无描述。系统推荐的高质量记忆内容，适合每天坚持背诵学习。
卡片预览 (17 张)
Define time complexity
time it takes for a program to run
Define space complexity
memory that is required
Define Big O Notation
allows us to compare one algorithm to another as to choose the best option
How to calculate Big O
-take the highest power e.g. 3n^3 + 4n^2 O(n^3)
What is the Big O for constant time complexity
O(1)
What is Big O for linear search
O(n)
What is Big O for binary search
O(logn)
What is Big O for Binary tree search
O(logn)
What is Big O for Bubble sort
O(n^2)
What is Big O for Merge sort
O(nlogn)
What is the order of complexities?
• Constant • Logarithmic • Linear • Polynomial • Exponential • Factorial ‘Complexities love licking p*nises, especially Flynn’s’
Define intractable
it is too complex to be solved in polynomial time, heuristic methods can be used to find a ‘good enough’ solution (DIFFERENT TO UNSOLVABLE)
Define heuristic method
practical methods to find a sufficient, but not optimal solution
Define halting problem
• used by Alan Turing as proof that some problems are unsolvable for a computer • tell if program will halt without running it
What is Big O for Travelling salesman
O(n!)
What is Big O for dynamic programming Travelling Salesman
O(a^n)
What is big O for Hash table
O(1)