Asymptotic Notation
উপগামী সংকেত
Input বড় হলে একটা algorithm-এর cost কীভাবে বাড়ে সেটা প্রকাশের ভাষা — O, Θ, Ω। ধ্রুবক আর ছোট পদ বাদ দিয়ে শুধু বৃদ্ধির হার দেখায়।
also: Big O, big-o, complexity notation
Asymptotic notation একটা প্রশ্নের উত্তর দেয়: input দ্বিগুণ করলে কাজ কতগুণ বাড়বে?
এটা wall-clock time মাপে না। মাপে বৃদ্ধির হার।
| সংকেত | অর্থ | সাধারণ ভাষায় |
|---|---|---|
O(f) | উপরের সীমা | “এর চেয়ে খারাপ হবে না” |
Ω(f) | নিচের সীমা | “এর চেয়ে ভালো হবে না” |
Θ(f) | দুই দিকেই আঁটসাঁট | “ঠিক এতটাই” |
o(f) | কঠোর উপরের সীমা | “এর চেয়ে কঠোরভাবে ভালো” |
যেটা এটা লুকিয়ে রাখে
O(n) আর O(n) সমান নয় বাস্তবে। একটা linked list traversal আর একটা array
traversal — দুটোই O(n), কিন্তু array-টা ১০–৫০ গুণ দ্রুত হতে পারে, কারণ
cache locality।
তাই asymptotic analysis দিয়ে শুরু করুন, শেষ করবেন না। Level 11-এ আমরা দেখব কেন theoretical complexity আর measured performance প্রায়ই মেলে না।