نکته : در پیچیدگی زمانی یک الگوریتم اگر حلقه های forتو در تو باشند یعنی به هم وابسته نباشند در هم ضرب میشوند ولی زمانی که بصورت مجذا از هم باشند با یکدیگر جمع میشوند.
📣👨💻 @AlgorithmDesign_DataStructuer
📣👨💻 @AlgorithmDesign_DataStructuer
👍4👨💻1
همان طور که مشاهده می کنید مجموع زمان اجرای این قطعه کد 2 میباشد و ما زمانی که پیچیدگی یک الگوریتم عدد ثباتی باشد آن را از مرتبه 1 در نظر میگیریم.
📣👨💻 @AlgorithmDesign_DataStructuer
📣👨💻 @AlgorithmDesign_DataStructuer
👍2👨💻1
Algorithm design & data structure
Photo
جواب :
در این سوال چون دو حلقه تو در تور داریم میتوان گفت که جواب n^2میباشد زیرا که مهم نیست که بازه حلقه فور ما از کجا شروع میشود.
📣👨💻 @AlgorithmDesign_DataStructuer
در این سوال چون دو حلقه تو در تور داریم میتوان گفت که جواب n^2میباشد زیرا که مهم نیست که بازه حلقه فور ما از کجا شروع میشود.
📣👨💻 @AlgorithmDesign_DataStructuer
👍4👨💻1
ویژگی توابع بازگشتی :
1 -از معایب توابع بازگشتی این است که در نهایت سادگی حجم زیادی را اشغال کرده و
نسبتا کند عمل می کنند و نیز در زمان پردازش cpu را درگیر می کنند.
2 -خود را فراخوانی می کنند.( تعداد دفعاتی که خود را فراخوانی می کند باید محدودباشد.بدیهی است که در غیر این صورت اجرای آن خاتمه نمی یابد.)
3 -دارای شرط خاتمه می باشد.
📣👨💻 @AlgorithmDesign_DataStructuer
1 -از معایب توابع بازگشتی این است که در نهایت سادگی حجم زیادی را اشغال کرده و
نسبتا کند عمل می کنند و نیز در زمان پردازش cpu را درگیر می کنند.
2 -خود را فراخوانی می کنند.( تعداد دفعاتی که خود را فراخوانی می کند باید محدودباشد.بدیهی است که در غیر این صورت اجرای آن خاتمه نمی یابد.)
3 -دارای شرط خاتمه می باشد.
📣👨💻 @AlgorithmDesign_DataStructuer
👌4👍2👨💻1
مرتبه تابع زیر از کدام یک از توابع می باشد؟
f(n)=6n+4n^2+6!
f(n)=6n+4n^2+6!
Anonymous Poll
5%
6n
10%
n
11%
6!
74%
n^2
👍3👨💻1
آرایه:
آرایـه نوعی ساختمان داده است که عناصر آن هم نوع بوده و هر یک از عناصر با یک اندیس به صورت مسـتقیم قابـل دسـتیابی اسـت. آرایـه مـیتواند یک بعدی , دو بعدی و یا چند بعدی باشد.آرایه های دو بعدی را با نام ماتریس میشناسیم.
[L1 … U1 , L2 … U2 , Ln … Un]
Array [L … U]
size of Array = U-L+1
[ U1 – L1 + 1][U2 – L2 + 1][Un – Ln + 1]
Space required for the array = n × (U-L+1)
📣👨💻 @AlgorithmDesign_DataStructuer
آرایـه نوعی ساختمان داده است که عناصر آن هم نوع بوده و هر یک از عناصر با یک اندیس به صورت مسـتقیم قابـل دسـتیابی اسـت. آرایـه مـیتواند یک بعدی , دو بعدی و یا چند بعدی باشد.آرایه های دو بعدی را با نام ماتریس میشناسیم.
[L1 … U1 , L2 … U2 , Ln … Un]
Array [L … U]
size of Array = U-L+1
[ U1 – L1 + 1][U2 – L2 + 1][Un – Ln + 1]
Space required for the array = n × (U-L+1)
📣👨💻 @AlgorithmDesign_DataStructuer
👍5👨💻1
درخت جست و جوی دودویی(BST):
درخت جستجو دودویی یک درخت دودیی است که در آن هر گره از تمام کلید های زیر درخت چپ بزرگتر و از تمام کلید های زیر درخت راست کوچیک تر است.
📣👨💻 @AlgorithmDesign_DataStructuer
درخت جستجو دودویی یک درخت دودیی است که در آن هر گره از تمام کلید های زیر درخت چپ بزرگتر و از تمام کلید های زیر درخت راست کوچیک تر است.
📣👨💻 @AlgorithmDesign_DataStructuer
👌3👍1👨💻1
Algorithm design & data structure
مرتبه تابع زیر از کدام یک از توابع می باشد؟
f(n)=6n+4n^2+6!
f(n)=6n+4n^2+6!
جواب:
نکته:طبق اصل maxگیری , وقتی بین چند جمله جمع یا تفریق وجود دارد,مرتبه آن برابر با بزرگترین جمله آن است .
بنابراین بزرگترین جمله در این تابع n^2می باشد.
📣👨💻 @AlgorithmDesign_DataStructuer
نکته:طبق اصل maxگیری , وقتی بین چند جمله جمع یا تفریق وجود دارد,مرتبه آن برابر با بزرگترین جمله آن است .
بنابراین بزرگترین جمله در این تابع n^2می باشد.
📣👨💻 @AlgorithmDesign_DataStructuer
👌8👨💻1
نماد O بزرگ:
یک نماد ریاضی است که برای رفتار حدی یک تابع به کار می رود. این نماد که مخفف Order of growthکه به فارسی به معنای مرتبه رشد هست برای رشد الگوریتم ها به کار گرفته میشود که در وقع میتوان گفت که به معنای کران بالای رشد توابع به کار رفته در الگوریتم ها به کار می رود.
تحلیل شکل:
در واقع میگه از یک مقدار خاصی Xoبیشتر ,تابع gبا ضریب cمقدار بیشتری یا مساوی از تابع fمی باشد.
📣👨💻 @AlgorithmDesign_DataStructuer
یک نماد ریاضی است که برای رفتار حدی یک تابع به کار می رود. این نماد که مخفف Order of growthکه به فارسی به معنای مرتبه رشد هست برای رشد الگوریتم ها به کار گرفته میشود که در وقع میتوان گفت که به معنای کران بالای رشد توابع به کار رفته در الگوریتم ها به کار می رود.
تحلیل شکل:
در واقع میگه از یک مقدار خاصی Xoبیشتر ,تابع gبا ضریب cمقدار بیشتری یا مساوی از تابع fمی باشد.
📣👨💻 @AlgorithmDesign_DataStructuer
👍5👨💻1
الگوریتم های بازگشتی داری چه معایبی هستند؟
Anonymous Quiz
63%
اتلاف حافظه،عدم بهینه بودن
10%
قابل فهم بودن،طولانی بودن الگوریتم
12%
هیچ کدام
15%
رفع تکرار و تکرار استفاده از کد
👍4👨💻2
چه طوری الگوریتم یک مسأله را پیدا کنید؟
سوالی که برای خیلی از ما پیش میاد اینکه برای حل یک سوال چه طوری باید الگوریتم آن را بدست بیاریم .راه حل برای بدست آوردن الگوریتم یک مسأله به صورت زیر میباشد:
1-ایده
2-پیاده کردن ایده
3-از درست بوده ایده اطمینان خاطر کنیم
4-پیچیدگی آن را بدست آوریم
5-بعد از انجام مراحل بالا با استفاده از یکی از زبان های برنامه نویسی آن را تست کنیم
با استفاه از مراحل بالا که ذکر شد می توان الگوریتم درست کنیم البته ما به دنبال کمترین هزینه برای الگوریتم هستیم که بعدا به برخی از الگوریتم های معرفت میپردازیم.
📣👨💻 @AlgorithmDesign_DataStructuer
سوالی که برای خیلی از ما پیش میاد اینکه برای حل یک سوال چه طوری باید الگوریتم آن را بدست بیاریم .راه حل برای بدست آوردن الگوریتم یک مسأله به صورت زیر میباشد:
1-ایده
2-پیاده کردن ایده
3-از درست بوده ایده اطمینان خاطر کنیم
4-پیچیدگی آن را بدست آوریم
5-بعد از انجام مراحل بالا با استفاده از یکی از زبان های برنامه نویسی آن را تست کنیم
با استفاه از مراحل بالا که ذکر شد می توان الگوریتم درست کنیم البته ما به دنبال کمترین هزینه برای الگوریتم هستیم که بعدا به برخی از الگوریتم های معرفت میپردازیم.
📣👨💻 @AlgorithmDesign_DataStructuer
👌7👍2👨💻1
Algorithm design & data structure
الگوریتم های بازگشتی داری چه معایبی هستند؟
جواب:
همان طور که مشاهده می کنید جواب گزینه 1 می باشد.
الگوریتم های بازگشتی دارای مزایای زیادی هستند به همان صورت هم دارای معایبی هستند که از آن ها میتوان به اتلاف حافظه یعنی فضای زیادی را اشغال میکنند,عدم بهینه بودن آن ها یعنی ما میتوانم آن مسأله را با الگوریتم بهینه تر با هزینه کمتر حل کنیم ,همچینن میتوان به زمان اجرای بالای آن ها پرداخت که بعضی از الگوریتم های بازگشتی زمان اجرای زیادی دارند و ممکن است هزینه زیادی برای ما داشته باشد.
📣👨💻 @AlgorithmDesign_DataStructuer
همان طور که مشاهده می کنید جواب گزینه 1 می باشد.
الگوریتم های بازگشتی دارای مزایای زیادی هستند به همان صورت هم دارای معایبی هستند که از آن ها میتوان به اتلاف حافظه یعنی فضای زیادی را اشغال میکنند,عدم بهینه بودن آن ها یعنی ما میتوانم آن مسأله را با الگوریتم بهینه تر با هزینه کمتر حل کنیم ,همچینن میتوان به زمان اجرای بالای آن ها پرداخت که بعضی از الگوریتم های بازگشتی زمان اجرای زیادی دارند و ممکن است هزینه زیادی برای ما داشته باشد.
📣👨💻 @AlgorithmDesign_DataStructuer
👍4👨💻3👏2
صف(Queue):
صف یک ساختار داده انتزاعی است که تا حدودی شبیه به Stacks است. برخلاف پشته ها، یک صف در هر دو انتهای آن باز است. یک سر همیشه برای درج داده ها (enqueue) و دیگری برای حذف داده ها (dequeue) استفاده می شود. صف از First-In-First-Out پیروی می کند، به عنوان مثال، آیتم داده ای که ابتدا ذخیره شده است، ابتدا قابل دسترسی خواهد بود.
یک مثال واقعی از صف می تواند یک جاده یک طرفه تک خطی باشد، جایی که وسیله نقلیه ابتدا وارد می شود، اول از آن خارج می شود. نمونه های واقعی بیشتری را می توان به عنوان صف در پنجره های بلیط و ایستگاه های اتوبوس مشاهده کرد.
📣👨💻 @AlgorithmDesign_DataStructuer
صف یک ساختار داده انتزاعی است که تا حدودی شبیه به Stacks است. برخلاف پشته ها، یک صف در هر دو انتهای آن باز است. یک سر همیشه برای درج داده ها (enqueue) و دیگری برای حذف داده ها (dequeue) استفاده می شود. صف از First-In-First-Out پیروی می کند، به عنوان مثال، آیتم داده ای که ابتدا ذخیره شده است، ابتدا قابل دسترسی خواهد بود.
یک مثال واقعی از صف می تواند یک جاده یک طرفه تک خطی باشد، جایی که وسیله نقلیه ابتدا وارد می شود، اول از آن خارج می شود. نمونه های واقعی بیشتری را می توان به عنوان صف در پنجره های بلیط و ایستگاه های اتوبوس مشاهده کرد.
📣👨💻 @AlgorithmDesign_DataStructuer
👨💻2👍1
👨💻3
جست و جوی خطی در ارایه ها:
تابع بالا مقدار Xرا در آرایه n عنصریA ,به روش مقایسه تک تک عناصر آرایه , جست و جو می کند .در صورت وجود اندیس آرایه (خانه حاوی X) و در صورت پیدا نکردن آن عدد1- را بر می گرداند.
📣👨💻 @AlgorithmDesign_DataStructuer
تابع بالا مقدار Xرا در آرایه n عنصریA ,به روش مقایسه تک تک عناصر آرایه , جست و جو می کند .در صورت وجود اندیس آرایه (خانه حاوی X) و در صورت پیدا نکردن آن عدد1- را بر می گرداند.
📣👨💻 @AlgorithmDesign_DataStructuer
🙏3👍1👨💻1
الگوریتم های تقسیم و غلبه(ِDivide and Conquer):
روش تقسیم و غلبه,یک روش بالا و پایین (Top-Down)است.برای حل یک نمونه مسأله کلی ابتدا با تقسیم آن مسأله به زیر مسأله های کوچک تر(قابل حل) تلاش برای حل زیر مسأله ها شروع شده و نهایتاََ مسأله کلی نیز با حل زیر مسأله ها حل می شود .اصولا این روش به یک الگوریتم بازگشتی منجر می شود.
📣👨💻 @AlgorithmDesign_DataStructuer
روش تقسیم و غلبه,یک روش بالا و پایین (Top-Down)است.برای حل یک نمونه مسأله کلی ابتدا با تقسیم آن مسأله به زیر مسأله های کوچک تر(قابل حل) تلاش برای حل زیر مسأله ها شروع شده و نهایتاََ مسأله کلی نیز با حل زیر مسأله ها حل می شود .اصولا این روش به یک الگوریتم بازگشتی منجر می شود.
📣👨💻 @AlgorithmDesign_DataStructuer
👍3👨💻2