|
1.求1+2+3+......+100
循环累加
package main
import "fmt"
func main() {
sum, n := 0, 100
for i:=1;i<=n;i++ {
sum = sum + i
}
fmt.Printf("%d", sum)
}
高斯算法求和
相当于等差数列求和
package main
import "fmt"
func main() {
sum, n := 0, 100
sum = (1 + n) * n / 2
fmt.Printf("%d", sum)
}
2.7 算法效率的度量方法
事后统计方法
事前分析估算方法
package main
import "fmt"
func main() {
x, sum, n := 0, 0, 100 //执行1次
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
x++ //执行1次
sum = sum + x
}
}
fmt.Printf("%d", sum) //执行1次
}
2.8 函数的渐近增长
2.9 算法时间复杂度
我们的三个求和算法的时间复杂度分别为O（n），O（1），O（n^2）。O（1）叫常数阶，O（1）叫线性阶，O（n^2）叫平方阶。
2.9.2 推导大O阶方法
2.9.3 常数阶
2.9.4 线性阶
2.9.5 对数阶
下面这对代码，时间复杂度是多少？
package main
import "fmt"
func main() {
count, n := 1, 100
for count < n {
count = count * 2
//时间复杂度为O（1）的程序步骤序列
}
}
2^x=n，x=log2 n真数，所以这个循环的时间复杂度是O（logn）。
2.9.6 平方阶
2.10 常见的时间复杂度
2.11 最坏情况和平均情况
2.12 算法空间时间复杂度
要判断某某年是不是闰年
判断一个年份是否是闰年，需要满足下面条件之一：
年份能被4整除，但不能被100整除；
能被400整除
package main
import (
"fmt"
)
func main() {
var year int
fmt.println("请输入年份：")
fmt.Scanln(&year)
if (year%4==0 &&year%100!=0) || year%400==0 {
fmt.println(year, "是闰年。")
} else {
fmt.println(year, "不是闰年。")
}
}
2.13 总结回顾
第3章 线性表
要实现两个线性表集合A和B的并集操作
//两个集合取并集
package main
import "fmt"
//思想:
//运用map,统计nums1中值出现的次数，即map[值]次数
//遍历nums2中的值,查看值是否在map中的出现
func union(num1, num2 []string) []string {
m := make(map[string]int)
for _, v := range num1 {
m[v]++
}
fmt.Println(m)
for _, v := range num2 {
// times, bool := m[v]
// if bool != true {
// fmt.Println("不存在")
// }
times, _ := m[v]
fmt.Printf("v=%s,times=%d\n", v, times)
if times == 0 {
num1 = append(num1, v)
}
}
return num1
}
func main() {
num1 := []string{"3", "4", "1"}
num2 := []string{"2", "1", "3"}
fmt.Println(union(num1,num2))
}
package model
import (
"sort"
"sync"
)
type Set struct {
sync.RWMutex
m map[int]bool
}
// 新建集合对象
func New(items ...int) *Set {
s := &Set{
m: make(map[int]bool, len(items)),
}
s.Add(items...)
return s
}
// 添加元素
func (s *Set) Add(items ...int) {
s.Lock()
defer s.Unlock()
for _, v := range items {
s.m[v] = true
}
}
// 删除元素
func (s *Set) Remove(items ...int) {
s.Lock()
defer s.Unlock()
for _, v := range items {
delete(s.m, v)
}
}
// 判断元素是否存在
func (s *Set) Has(items ...int) bool {
s.RLock()
defer s.RUnlock()
for _, v := range items {
if _, ok := s.m[v]; !ok {
return false
}
}
return true
}
// 元素个数
func (s *Set) Count() int {
return len(s.m)
}
// 清空集合
func (s *Set) Clear() {
s.Lock()
defer s.Unlock()
s.m = map[int]bool{}
}
// 空集合判断
func (s *Set) Empty() bool {
return len(s.m) == 0
}
// 无序列表
func (s *Set) List() []int {
s.RLock()
defer s.RUnlock()
list := make([]int, 0, len(s.m))
for item := range s.m {
list = append(list, item)
}
return list
}
// 排序列表
func (s *Set) SortList() []int {
s.RLock()
defer s.RUnlock()
list := make([]int, 0, len(s.m))
for item := range s.m {
list = append(list, item)
}
sort.Ints(list)
return list
}
// 并集
func (s *Set) Union(sets ...*Set) *Set {
r := New(s.List()...)
for _, set := range sets {
for e := range set.m {
r.m[e] = true
}
}
return r
}
// 差集
func (s *Set) Minus(sets ...*Set) *Set {
r := New(s.List()...)
for _, set := range sets {
for e := range set.m {
if _, ok := s.m[e]; ok {
delete(r.m, e)
}
}
}
return r
}
// 交集
func (s *Set) Intersect(sets ...*Set) *Set {
r := New(s.List()...)
for _, set := range sets {
for e := range s.m {
if _, ok := set.m[e]; !ok {
delete(r.m, e)
}
}
}
return r
}
// 补集
func (s *Set) Complement(full *Set) *Set {
r := New()
for e := range full.m {
if _, ok := s.m[e]; !ok {
r.Add(e)
}
}
return r
}
3.4 线性表的顺序存储结构
3.5 顺序存储结构的插入与删除
3.5.1 获得元素操作
package main
import (
"errors"
)
type ElemType int
const MAXSIZE = 20
type SqList struct {
data [MAXSIZE] ElemType
length int
}
//获取数据元素
func GetElem(s SqList, i int) (err error, res ElemType) {
if s.length == 0 || i < 0 || i > s.length {
err = errors.New("查找失败")
}
res = s.data[i]
return
}
3.5.2 插入操作
//插入数据
func ListInsert(s *SqList, i int, e *ElemType) error{
if s.length == MAXSIZE {
return errors.New("线性表已满，不能插入数据")
}
if i < 0 || i > s.length {
return errors.New("插入的位置不正确")
}
//i位开始后移一位
//从最后一位向前遍历到第i位
for j := s.length; j>=i; j-- {
s.data[j+1] = s.data[j]
}
s.data[i] = *e
s.length++
return nil
}
3.5.3 删除操作
//删除数据
func ListDelete(s SqList, i int) (err error) {
if s.length == 0 {
err = errors.New("线性表为空")
}
if i < 0 || i > s.length-1 {
err = errors.New("删除的位置不正确")
}
//从删除元素位置开始向后遍历到最后一个位置，分别将他们向前移动一位
for j := i; j < s.length-1; j++ {
s.data[j] = s.data[j+1]
}
s.data[s.length-1] = 0 //清除数据
s.length--
return
}
3.5.4 线性表顺序存储结构的优缺点
3.6 线性表的链式存储结构
|