آموزش تحلیل پیچیدگی زمان و مکان (نشانگذاری Big-O)

سرفصل ها و درس ها

مبانی تحلیل پیچیدگی Complexity analysis basics

• معرفی Introduction

• مثال ها Examples

• نمادهای Big-O، big-Ω و big-θ Big-O, big-Ω, and big-θ notations

• منبع اضافی: نمادها تعریف ریاضی Extra resource: Notations mathematical definition

• مسابقه: نمادهای Big-O، big-Ω و big-θ Quiz: Big-O, big-Ω, and big-θ notations

• بهترین، متوسط ​​و بدترین حالت Best, average, and worst case

• کلاس های پیچیدگی Complexity classes

نحوه تجزیه و تحلیل پیچیدگی یک الگوریتم How to analyze the complexity of an algorithm

• سلسله مراتب پیچیدگی ها Complexities hierarchy

• امتحان: پیچیدگی را تجزیه و تحلیل کنید Quiz: Analyze the complexity

• نحوه تجزیه و تحلیل پیچیدگی یک الگوریتم How to analyze the complexity of an algorithm

• آزمون: پیچیدگی را از T(n) استنتاج کنید Quiz: Deduce the complexity from T(n)

• پیچیدگی مستهلک شده Amortized complexity

• نحوه مقایسه دو الگوریتم How to compare two algorithms

• تجزیه و تحلیل مسئله "جفتی را پیدا کنید که جمع آن k باشد". "Find pair that sums up to k" problem analysis

الگوریتم های جستجو و تحلیل پیچیدگی Searching algorithms and complexity analysis

• الگوریتم جستجوی خطی Linear search algorithm

• الگوریتم جستجوی باینری Binary search algorithm

• الگوریتم Knuth-Morris-Pratt (KMP). Knuth-Morris-Pratt (KMP) algorithm

الگوریتم های مرتب سازی و تحلیل پیچیدگی Sorting algorithms and complexity analysis

• معرفی Introduction

• مرتب سازی درج Insertion sort

• مرتب سازی حبابی Bubble sort

• مرتب سازی انتخابی Selection sort

• مرتب سازی ادغام Merge sort

• Heapsort Heapsort

• مرتب سازی سریع Quicksort

• مرتب سازی شمارش Counting sort

• مرتب سازی رادیکس Radix sort

• مرتب سازی سطلی Bucket sort

• مرتب سازی پوسته Shell sort

• منبع اضافی: خلاصه Extra resource: Summary

توابع بازگشتی و تحلیل پیچیدگی Recursive functions and complexity analysis

• معرفی Introduction

• روش درخت بازگشتی Recursion tree method

• روش رابطه عود Recurrence relation method

• روش قضیه استاد Master theorem method

• تحلیل پیچیدگی فضایی توابع بازگشتی Space complexity analysis of recursive functions

• حفظ کردن Memoization

• برنامه نویسی پویا Dynamic programming

ساختار داده ها و تحلیل پیچیدگی Data structures and complexity analysis

• آرایه ها Arrays

• لیست ها، پشته ها و صف های مرتبط Linked lists, stacks, and queues

• جداول و ست ها هش کنید Hash tables and sets

• درختان Trees

• اثبات ریاضی پیچیدگی زمانی ساخت یک پشته باینری Mathematical proof of time complexity of building a binary heap

• نمودارها Graphs

• منبع اضافی: خلاصه Extra resource: Summary

اشتباهات رایج و باورهای غلط Common mistakes and misconceptions

• حلقه های تو در تو == O(n²)؟ Nested loops == O(n²)?

• اشتباهات رایج Common mistakes

• آیا همیشه نیاز به بهینه سازی داریم؟ Do we always need to optimize?

تمرین: تجزیه و تحلیل پیچیدگی راه حل مشکلات مصاحبه کدنویسی محبوب Practice: complexity analysis of popular coding interview problems solutions

• امتحان: پیچیدگی مسئله "اولین شخصیت تکرار شونده" را تجزیه و تحلیل کنید Quiz: Analyze the complexity of "First repeating character" problem

• اولین شخصیت تکراری First repeating character

• آزمون: پیچیدگی مسئله "حداکثر زیرآرایه" را تجزیه و تحلیل کنید Quiz: Analyze the complexity of "Maximum subarray" problem

• حداکثر زیرآرایه Maximum subarray

• امتحان: پیچیدگی مسئله "پیک یابی" را تجزیه و تحلیل کنید Quiz: Analyze the complexity of "Peak finding" problem

• اوج یابی Peak finding

• امتحان: پیچیدگی مشکل "لیست پیوند شده پالیندروم" را تجزیه و تحلیل کنید Quiz: Analyze the complexity of "Palindrome linked list" problem

• فهرست پیوندی پالیندروم Palindrome linked list

• امتحان: پیچیدگی مسئله "زیر دنباله های رشته" را تجزیه و تحلیل کنید Quiz: Analyze the complexity of "String subsequences" problem

• دنباله های رشته ای String subsequences

• آزمون: پیچیدگی مسئله "مسیر حداقل هزینه" را تجزیه و تحلیل کنید Quiz: Analyze the complexity of "Minimum cost path" problem

• مسیر حداقل هزینه Minimum cost path

• امتحان: پیچیدگی مسئله "طولانی ترین دنباله متوالی" را تجزیه و تحلیل کنید Quiz: Analyze the complexity of "Longest consecutive sequence" problem

• طولانی ترین سکانس متوالی Longest consecutive sequence

• امتحان: پیچیدگی مسئله "طولانی ترین دنباله مشترک" را تجزیه و تحلیل کنید Quiz: Analyze the complexity of "Longest common subsequence" problem

• طولانی ترین دنباله متداول Longest common subsequence

• امتحان: پیچیدگی مسئله "زیر مجموعه هایی که به k جمع می شوند" را تجزیه و تحلیل کنید Quiz: Analyze the complexity of "Subsets that sum up to k" problem

• زیرمجموعه هایی که جمع آنها k می شود Subsets that sum up to k

• امتحان: پیچیدگی مسئله "درخت باینری متعادل" را تجزیه و تحلیل کنید Quiz: Analyze the complexity of "Balanced binary tree" problem

• درخت باینری متعادل Balanced binary tree

• امتحان: پیچیدگی مسئله "جایگشت آرایه" را تجزیه و تحلیل کنید Quiz: Analyze the complexity of "Array permutations" problem

• جایگشت آرایه ها Array permutations

• امتحان: پیچیدگی مشکل "جستجوی کلمه" را تجزیه و تحلیل کنید Quiz: Analyze the complexity of "Word search" problem

• جستجوی کلمه Word search

• امتحان: پیچیدگی مسئله "N-queens" را تجزیه و تحلیل کنید Quiz: Analyze the complexity of "N-queens" problem

• N-ملکه ها N-queens

• امتیاز: برنامه نویسی پویا بهینه شده برای فضا Bonus: space-optimized dynamic programming