рдХрд┐рд╕реА algorithm рдХреА Complexity рдПрдХ Function рд╣реЛрддрд╛ рд╣реИ рдЬреЛ рдХрд┐рд╕реА input data рдХреЗ рдЖрдзрд╛рд░ рдкрд░ data рдХреА┬а Process рдореЗрдВ рд▓рдЧрдиреЗ рд╡рд╛рд▓реЗ рд╕рдордп рдпрд╛ рд╕реНрдкреЗрд╕ рдпрд╛ рджреЛрдиреЛрдВ рджрд░реНрд╢рд╛рддрд╛ рд╣реИ| рдЗрд╕реА рдХреЗ рдЖрдзрд╛рд░ рдкрд░ Complexity рдХреЛ рджреЛ рднрд╛рдЧреЛрдВ рдореЗрдВ рдмрд╛рдВрдЯрд╛ рдЬрд╛рддрд╛ рд╣реИ
1.Time (рд╕рдордп) Complexity
2.Space (рд╕реНрдкреЗрд╕) Complexity
┬а
1. Time (рд╕рдордп) Complexity
рдПрдХ algorithm рдХреА time complexity, рдЕрд▓реНрдЧреЛрд░рд┐рдердо рдХреЗ рджреНрд╡рд╛рд░рд╛ рдЕрдкрдиреА process рдХреЛ рдкреВрд░рд╛ рдХрд░рдиреЗ рдореЗрдВ рд▓рдЧрдиреЗ рд╡рд╛рд▓реЗ рдХреБрд▓ рд╕рдордп рдХреА рдорд╛рддреНрд░рд╛ рд╣реИ. рдЬреНрдпрд╛рджрд╛рддрд░ рдЕрд▓реНрдЧреЛрд░рд┐рдердо рдХреА рдЯрд╛рдЗрдо рдХреЙрдореНрдкреНрд▓реЗрдХреНрд╕рд┐рдЯреА рдХреЛ Big O notation рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рдХреЗ рд╡реНрдпрдХреНрдд рдХрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИред рдпрд╣ рдПрдХ asymptotic notation рд╣реИ. рдЗрд╕рдХреЛ рд╡реНрдпрдХреНрдд рдХрд░рдиреЗ рдХреЗ рд╕рднреА notations рдирд┐рдореНрдирд▓рд┐рдЦрд┐рдд рд╣реИ.
Big O тАУ O(n),
Bi.g Theta тАУ┬а ╬Ш(n)
Big Omega тАУ ╬й(n)
execution рдХреЛ рд╕рдорд╛рдкреНрдд рдХрд░рдиреЗ рдХреЗ рд▓рд┐рдП рдХрд┐рд╕реА рднреА рдПрд▓реНрдЧреЛрд░рд┐рдердо рджреНрд╡рд╛рд░рд╛ perform рдХрд┐рдпреЗ рдЧрдП steps рдХреА рд╕рдВрдЦреНрдпрд╛ рдХреА рдЧрд┐рдирддреА (counting) рдХреЗ рджреНрд╡рд╛рд░рд╛ time complexity рдХреЛ estimate рдХрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИ.
┬а
2. Space (рд╕реНрдкреЗрд╕) Complexity
рдПрдХ algorithm рдХреА space complexity рдЕрд▓реНрдЧреЛрд░рд┐рдердо рдХреЗ рджреНрд╡рд╛рд░рд╛ рд▓реА рдЧрдпреА space рдХреА рдорд╛рддреНрд░рд╛ рд╣реИ. рд╕реНрдкреЗрд╕ рдХреЙрдореНрдкреНрд▓реЗрдХреНрд╕рд┐рдЯреА рдХреЗ рдЕрдВрджрд░ auxiliary space рддрдерд╛ input рдХреЗ рджреНрд╡рд╛рд░рд╛ use рд▓рд┐рдпрд╛ рдЧрдпрд╛ space рджреЛрдиреЛрдВ рдЖрддреЗ рд╣реИрдВ.
Auxiliary space рдЬреЛ рд╣реИ рд╡рд╣ algorithm рдХреЗ рджреНрд╡рд╛рд░рд╛ execution рдХреЗ рджреМрд░рд╛рди рдкреНрд░рдпреЛрдЧ рдХрд┐рдпрд╛ рдЧрдпрд╛ temporary space рдпрд╛ extra space рд╣реЛрддрд╛ рд╣реИ.
рдПрдХ рдЕрд▓реНрдЧреЛрд░рд┐рдердо рдХреА space complexity рдХреЛ Big O (O(n)) notation рдХреЗ рджреНрд╡рд╛рд░рд╛ рд╡реНрдпрдХреНрдд рдХрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИ.
рдмрд╣реБрдд рд╕рд╛рд░реАрдВ algorithms рдХреЗ рдкрд╛рд╕ inputs рд╣реЛрддреЗ рд╣реИрдВ рдЬреЛ size рдореЗрдВ рднрд┐рдиреНрди рднрд┐рдиреНрди рд╣реЛрддреЗ рд╣реИрдВ. рдРрд╕реА рд╕реНрдерд┐рддрд┐ рдореЗрдВ space complexity рдЬреЛ рд╣реИ рд╡рд╣ input рдХреЗ size рдкрд░ рдирд┐рд░реНрднрд░ рд░рд╣рддреА рд╣реИ.