ডেভসংকেত

অ্যালগরিদম কমপ্লেক্সিটি

বেশী ব্যবহৃত অ্যালগরিদম আর ডাটা স্ট্রাকচার ও তাদের মধ্যকার অপারেশনের বিগ-ও(Big-O) কমপ্লেক্সিটি সবগুলো একসাথে

কন্ট্রিবিউটর

শেয়ার করুন

প্রিন্ট করুন

অ্যারে(Array)

অ্যাক্সেস করতে(এভারেজ)
```
O(1)
```
অ্যাক্সেস করতে(সবচেয়ে খারাপ)
```
O(1)
```
সার্চ করতে(এভারেজ)
```
O(n)
```
সার্চ করতে(সবচেয়ে খারাপ)
```
O(n)
```
নতুন ইলিমেন্ট ঢুকাতে(এভারেজ)
```
O(n)
```
নতুন ইলিমেন্ট ঢুকাতে(সবচেয়ে খারাপ)
```
O(n)
```
ইলিমেন্ট ডিলেট করতে(এভারেজ)
```
O(n)
```
ইলিমেন্ট ডিলেট করতে(সবচেয়ে খারাপ)
```
O(n)
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

কিউ(Queue)

অ্যাক্সেস করতে(এভারেজ)
```
O(n)
```
অ্যাক্সেস করতে(সবচেয়ে খারাপ)
```
O(n)
```
সার্চ করতে(এভারেজ)
```
O(n)
```
সার্চ করতে(সবচেয়ে খারাপ)
```
O(n)
```
নতুন ইলিমেন্ট ঢুকাতে(এভারেজ)
```
O(1)
```
নতুন ইলিমেন্ট ঢুকাতে(সবচেয়ে খারাপ)
```
O(1)
```
ইলিমেন্ট ডিলেট করতে(এভারেজ)
```
O(1)
```
ইলিমেন্ট ডিলেট করতে(সবচেয়ে খারাপ)
```
O(1)
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

Doubly-Linked List

অ্যাক্সেস করতে(এভারেজ)
```
O(n)
```
অ্যাক্সেস করতে(সবচেয়ে খারাপ)
```
O(n)
```
সার্চ করতে(এভারেজ)
```
O(n)
```
সার্চ করতে(সবচেয়ে খারাপ)
```
O(n)
```
নতুন ইলিমেন্ট ঢুকাতে(এভারেজ)
```
O(1)
```
নতুন ইলিমেন্ট ঢুকাতে(সবচেয়ে খারাপ)
```
O(1)
```
ইলিমেন্ট ডিলেট করতে(এভারেজ)
```
O(1)
```
ইলিমেন্ট ডিলেট করতে(সবচেয়ে খারাপ)
```
O(1)
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

হ্যাশ(Hash) টেবিল

সার্চ করতে(এভারেজ)
```
Θ(1)
```
সার্চ করতে(সবচেয়ে খারাপ)
```
O(n)
```
নতুন ইলিমেন্ট ঢুকাতে(এভারেজ)
```
Θ(1)
```
নতুন ইলিমেন্ট ঢুকাতে(সবচেয়ে খারাপ)
```
O(n)
```
ইলিমেন্ট ডিলেট করতে(এভারেজ)
```
Θ(1)
```
ইলিমেন্ট ডিলেট করতে(সবচেয়ে খারাপ)
```
O(n)
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

কার্টেসিয়ান(Cartesian) ট্রি

সার্চ করতে(এভারেজ)
```
Θ(log(n))
```
সার্চ করতে(সবচেয়ে খারাপ)
```
O(n)
```
নতুন ইলিমেন্ট ঢুকাতে(এভারেজ)
```
Θ(log(n))
```
নতুন ইলিমেন্ট ঢুকাতে(সবচেয়ে খারাপ)
```
O(n)
```
ইলিমেন্ট ডিলেট করতে(এভারেজ)
```
Θ(log(n))
```
ইলিমেন্ট ডিলেট করতে(সবচেয়ে খারাপ)
```
O(n)
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

রেড-ব্ল্যাক ট্রি

অ্যাক্সেস করতে(এভারেজ)
```
Θ(log(n))
```
অ্যাক্সেস করতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
সার্চ করতে(এভারেজ)
```
Θ(log(n))
```
সার্চ করতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
নতুন ইলিমেন্ট ঢুকাতে(এভারেজ)
```
Θ(log(n))
```
নতুন ইলিমেন্ট ঢুকাতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
ইলিমেন্ট ডিলেট করতে(এভারেজ)
```
Θ(log(n))
```
ইলিমেন্ট ডিলেট করতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

এভিএল(AVL) ট্রি

অ্যাক্সেস করতে(এভারেজ)
```
Θ(log(n))
```
অ্যাক্সেস করতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
সার্চ করতে(এভারেজ)
```
Θ(log(n))
```
সার্চ করতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
নতুন ইলিমেন্ট ঢুকাতে(এভারেজ)
```
Θ(log(n))
```
নতুন ইলিমেন্ট ঢুকাতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
ইলিমেন্ট ডিলেট করতে(এভারেজ)
```
Θ(log(n))
```
ইলিমেন্ট ডিলেট করতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

কুইক সর্ট

সবচেয়ে ভালো
```
Ω(n log(n))
```
এভারেজ
```
Θ(n log(n))
```
সবচেয়ে খারাপ
```
O(n^2)
```
স্পেস কমপ্লেক্সিটি
```
O(log(n))
```

টিম সর্ট/টীম সর্ট

সবচেয়ে ভালো
```
Ω(n)
```
এভারেজ
```
Θ(n log(n))
```
সবচেয়ে খারাপ
```
O(n log(n))
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

বাবল সর্ট

সবচেয়ে ভালো
```
Ω(n)
```
এভারেজ
```
Θ(n^2)
```
সবচেয়ে খারাপ
```
O(n^2)
```
স্পেস কমপ্লেক্সিটি
```
O(1)
```

সিলেকশন সর্ট

সবচেয়ে ভালো
```
Ω(n^2)
```
এভারেজ
```
Θ(n^2)
```
সবচেয়ে খারাপ
```
O(n^2)
```
স্পেস কমপ্লেক্সিটি
```
O(1)
```

শেল সর্ট

সবচেয়ে ভালো
```
Ω(n log(n))
```
এভারেজ
```
Θ(n(log(n))^2)
```
সবচেয়ে খারাপ
```
O(n(log(n))^2)
```
স্পেস কমপ্লেক্সিটি
```
O(1)
```

রেডিক্স সর্ট

সবচেয়ে ভালো
```
Ω(nk)
```
এভারেজ
```
Θ(nk)
```
সবচেয়ে খারাপ
```
O(nk)
```
স্পেস কমপ্লেক্সিটি
```
O(n+k)
```

কিউব সর্ট

সবচেয়ে ভালো
```
Ω(n)
```
এভারেজ
```
Θ(n log(n))
```
সবচেয়ে খারাপ
```
Θ(n log(n))
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

এ স্টার সার্চ এলগোরিদম

গড়
```
O(|E|)
```
সবচেয়ে খারাপ
```
O(b^d)
```
স্পেস কমপ্লেক্সিটি
```
O((b^d)
```

বেলমান-ফোর্ড এলগোরিদম

গড়
```
O(|E| . |V|)
```
সবচেয়ে খারাপ
```
O(|E| . |V|)
```
স্পেস কমপ্লেক্সিটি
```
O(|V|)
```

টপোলজিকাল সর্ট

গড়
```
O(|V|+ |E|)
```
সবচেয়ে খারাপ
```
O(|V|+ |E|)
```
স্পেস কমপ্লেক্সিটি
```
O(|V|+ |E|)
```

ব্রেডথ-ফার্স্ট সার্চ (BFS) ট্রি

গড়
```
O(|V|+ |E|)
```
সবচেয়ে ভাল
```
O(|1|+ |E|)
```
সবচেয়ে খারাপ
```
O(|V|^2+ |E|)
```
স্পেস কমপ্লেক্সিটি
```
O(|V|)
```

ইউক্লিড্’স এলগোরিদম (Euclid's Algorithm) ২ সংখ্যার মধ্যে গসাগু

গড়
```
O(log(min(a, b))
```
সবচেয়ে ভাল
```
O(1)
```
সবচেয়ে খারাপ
```
O(logb)
```
স্পেস কমপ্লেক্সিটি
```
O(1)
```

স্ট্যাক(Stack)

অ্যাক্সেস করতে(এভারেজ)
```
O(n)
```
অ্যাক্সেস করতে(সবচেয়ে খারাপ)
```
O(n)
```
সার্চ করতে(এভারেজ)
```
O(n)
```
সার্চ করতে(সবচেয়ে খারাপ)
```
O(n)
```
নতুন ইলিমেন্ট ঢুকাতে(এভারেজ)
```
O(1)
```
নতুন ইলিমেন্ট ঢুকাতে(সবচেয়ে খারাপ)
```
O(1)
```
ইলিমেন্ট ডিলেট করতে(এভারেজ)
```
O(1)
```
ইলিমেন্ট ডিলেট করতে(সবচেয়ে খারাপ)
```
O(1)
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

Singly-Linked List

অ্যাক্সেস করতে(এভারেজ)
```
O(n)
```
অ্যাক্সেস করতে(সবচেয়ে খারাপ)
```
O(n)
```
সার্চ করতে(এভারেজ)
```
O(n)
```
সার্চ করতে(সবচেয়ে খারাপ)
```
O(n)
```
নতুন ইলিমেন্ট ঢুকাতে(এভারেজ)
```
O(1)
```
নতুন ইলিমেন্ট ঢুকাতে(সবচেয়ে খারাপ)
```
O(1)
```
ইলিমেন্ট ডিলেট করতে(এভারেজ)
```
O(1)
```
ইলিমেন্ট ডিলেট করতে(সবচেয়ে খারাপ)
```
O(1)
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

স্কিপ(Skip) লিস্ট

অ্যাক্সেস করতে(এভারেজ)
```
Θ(log(n))
```
অ্যাক্সেস করতে(সবচেয়ে খারাপ)
```
O(n)
```
সার্চ করতে(এভারেজ)
```
Θ(log(n))
```
সার্চ করতে(সবচেয়ে খারাপ)
```
O(n)
```
নতুন ইলিমেন্ট ঢুকাতে(এভারেজ)
```
Θ(log(n))
```
নতুন ইলিমেন্ট ঢুকাতে(সবচেয়ে খারাপ)
```
O(n)
```
ইলিমেন্ট ডিলেট করতে(এভারেজ)
```
Θ(log(n))
```
ইলিমেন্ট ডিলেট করতে(সবচেয়ে খারাপ)
```
O(n)
```
স্পেস কমপ্লেক্সিটি
```
O(n log(n))
```

বাইনারী সার্চ ট্রি

অ্যাক্সেস করতে(এভারেজ)
```
Θ(log(n))
```
অ্যাক্সেস করতে(সবচেয়ে খারাপ)
```
O(n)
```
সার্চ করতে(এভারেজ)
```
Θ(log(n))
```
সার্চ করতে(সবচেয়ে খারাপ)
```
O(n)
```
নতুন ইলিমেন্ট ঢুকাতে(এভারেজ)
```
Θ(log(n))
```
নতুন ইলিমেন্ট ঢুকাতে(সবচেয়ে খারাপ)
```
O(n)
```
ইলিমেন্ট ডিলেট করতে(এভারেজ)
```
Θ(log(n))
```
ইলিমেন্ট ডিলেট করতে(সবচেয়ে খারাপ)
```
O(n)
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

বি(B) ট্রি

অ্যাক্সেস করতে(এভারেজ)
```
Θ(log(n))
```
অ্যাক্সেস করতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
সার্চ করতে(এভারেজ)
```
Θ(log(n))
```
সার্চ করতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
নতুন ইলিমেন্ট ঢুকাতে(এভারেজ)
```
Θ(log(n))
```
নতুন ইলিমেন্ট ঢুকাতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
ইলিমেন্ট ডিলেট করতে(এভারেজ)
```
Θ(log(n))
```
ইলিমেন্ট ডিলেট করতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

স্প্লে(Splay) ট্রি

সার্চ করতে(এভারেজ)
```
Θ(log(n))
```
সার্চ করতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
নতুন ইলিমেন্ট ঢুকাতে(এভারেজ)
```
Θ(log(n))
```
নতুন ইলিমেন্ট ঢুকাতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
ইলিমেন্ট ডিলেট করতে(এভারেজ)
```
Θ(log(n))
```
ইলিমেন্ট ডিলেট করতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

কেডি(KD) ট্রি

অ্যাক্সেস করতে(এভারেজ)
```
Θ(log(n))
```
অ্যাক্সেস করতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
সার্চ করতে(এভারেজ)
```
Θ(log(n))
```
সার্চ করতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
নতুন ইলিমেন্ট ঢুকাতে(এভারেজ)
```
Θ(log(n))
```
নতুন ইলিমেন্ট ঢুকাতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
ইলিমেন্ট ডিলেট করতে(এভারেজ)
```
Θ(log(n))
```
ইলিমেন্ট ডিলেট করতে(সবচেয়ে খারাপ)
```
Θ(log(n))
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

মার্জ সর্ট

সবচেয়ে ভালো
```
Ω(n log(n))
```
এভারেজ
```
Θ(n log(n))
```
সবচেয়ে খারাপ
```
O(n log(n))
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

হিপ সর্ট

সবচেয়ে ভালো
```
Ω(n log(n))
```
এভারেজ
```
Θ(n log(n))
```
সবচেয়ে খারাপ
```
O(n log(n))
```
স্পেস কমপ্লেক্সিটি
```
O(1)
```

ইনসারশন সর্ট

সবচেয়ে ভালো
```
Ω(n)
```
এভারেজ
```
Θ(n^2)
```
সবচেয়ে খারাপ
```
O(n^2)
```
স্পেস কমপ্লেক্সিটি
```
O(1)
```

ট্রি সর্ট

সবচেয়ে ভালো
```
Ω(n log(n))
```
এভারেজ
```
Θ(n log(n))
```
সবচেয়ে খারাপ
```
O(n^2)
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

বাকেট সর্ট

সবচেয়ে ভালো
```
Ω(n+k)
```
এভারেজ
```
Θ(n+k)
```
সবচেয়ে খারাপ
```
O(n^2)
```
স্পেস কমপ্লেক্সিটি
```
O(n)
```

কাউন্টিং সর্ট

সবচেয়ে ভালো
```
Ω(n+k)
```
এভারেজ
```
Θ(n+k)
```
সবচেয়ে খারাপ
```
O(n+k)
```
স্পেস কমপ্লেক্সিটি
```
O(k)
```

ডায়াক্সট্রা এলগোরিদম

গড়
```
O(|E| log |V|)
```
সবচেয়ে খারাপ
```
O(|V|^2)
```
স্পেস কমপ্লেক্সিটি
```
O(|V|+ |E|)
```

প্রিম এলগোরিদম

গড়
```
O(|E| log |V|)
```
সবচেয়ে খারাপ
```
O(|V|^2)
```
স্পেস কমপ্লেক্সিটি
```
O(|V|+ |E|)
```

ফ্লোয়েড-ওয়ারশাল এলগোরিদম

গড়
```
O(|V|^3)
```
সবচেয়ে খারাপ
```
O(|V|^3)
```
স্পেস কমপ্লেক্সিটি
```
O(|V|^2)
```

ডেপ্ত ফার্স্ট সার্চ (DFS) ট্রি

গড়
```
O(|V|+ |E|)
```
সবচেয়ে ভাল
```
O(|1|+ |E|)
```
সবচেয়ে খারাপ
```
O(|V|^2+ |E|)
```
স্পেস কমপ্লেক্সিটি
```
O(|V|)
```

ফ্লাড ফিল (Flood Fill)

গড়
```
O(M x N)
```
সবচেয়ে ভাল
```
O(M x N)
```
সবচেয়ে খারাপ
```
O(M x N)
```
স্পেস কমপ্লেক্সিটি
```
O(M x N)
```